CS 1104 Introduction to Computer Science



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".



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.