## CS 1104 Introduction to Computer Science## COMPILERS AND TRANSLATORS |

**Syntactic Analysis**

The process of syntactic analysis is the reverse of generation, and generally uses the same syntax as for generation. Analysis can be performed "top-down" or "bottom-up", alternatively named "predictive analysis" or "reductive analysis".

**TOP-DOWN ANALYSIS**

Consider the syntactic specification for an expression:

<expr> ::= <term> + <expr> | <term>

<term> ::= <factor> * <term> |<factor>

<factor> ::= w | x | y | z | (<expr>)

And now the string:

w + x * z

Analyzing this from top-down requires that we are given the language_symbol that this is supposed to be. In this case we predict that this is an <expr>. The process is then to make substitutions as we did when generating a string and to continually compare the results with the string to be analyzed, checking out alternatives in a strict left-to-right order.

<expr> =>

<term> + <expr> =>

<factor> * <term> + <expr> =>

w * <term> + <expr>

At this stage, although the w matches with the string the * does not. So we must return to the point just before this substitution was made to see if there is an alternative. That is:

<term> + <expr> =>

<factor> + <expr> =>

w + <expr>

This time the first two characters match, and so we left with the question (sub-goal) of proving that the remainder of the string x * z is an instance of an <expr>. Eventually this can be proven.

The "derivation" of strings can be shown as a tree, where each portion of the tree represents a production rule with the left-hand-side at the top and the right-hand-side below it. The tree for the above expression is:

This process of analysis may be thought of as being analogous to solving jigsaw problems. Each production rule is akin to a jigsaw piece; each subtree in the syntactic tree is equivalent to a production rule.

Last updated 2001/03/13

© J.A.N. Lee, 2000-2001.