CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS

 

Language Generation from a Syntax

Consider the syntax:

<function_defn> ::=

(DEFINE (<function_name><space><parameter_list>) <s-exp>)

To define an "instance" of a function definition the procedure is simply to start with the language_symbol needed, locate its definition and then successively treat it as a "left-hand-side", and replace it by one of its its "right-hand-side" strings. In the following sequence the next item to be replaced is shown in red in each string.

<function_defn> =>

(DEFINE (<function_name><space><parameter_list>) <s-exp>)
=>

Substituting strictly** left-to-right:

(DEFINE ( QUICK <space><parameter_list>) <s-exp>) =>

(DEFINE ( QUICK  <parameter_list>) <s-exp>) =>

(DEFINE ( QUICK  <parameter_list><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  <parameter><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  <atom><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  <variable><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  <variable><alphanumeric_char><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  <alphabetic_char><alphanumeric_char><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  A<alphanumeric_char><space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  AF<space><parameter>) <s-exp>) =>

(DEFINE ( QUICK  AF <parameter>) <s-exp>) =>

(DEFINE ( QUICK  AF <atom>) <s-exp>) =>

(DEFINE ( QUICK  AF <variable>) <s-exp>) => ...

(DEFINE ( QUICK  AF GT) <s-exp>) =>

(DEFINE ( QUICK  AF GT) <LISP_function>) =>

(DEFINE ( QUICK  AF GT) (<function><space><argument_list>)) => ...

(DEFINE ( QUICK  AF GT) (+ AF GT))

At this point there are no further unresolved language_symbols and thus the generation process is complete.


** The compiler has to assume that substitutions have been made in some order to overcome ambiguities, and thus the strict left-to-right is commonly used.

[Prev][TOC][Next]

Last updated 00/11/08
© J.A.N. Lee, 2000.