2 * 3 - 4 * 1 ;First, lex partially recognises the input, recognising numbers, passing through operators etc., and discarding spaces, tabs and newlines.
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number |Then, the various yacc grammar rules are used:
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number | | | | | | | | | factor | factor | factor | factor |factors and *s are combined in terms:
term | factor | term | factor | \ | / | \ | / | term | term |but somehow, we have to transform the left-hand factors to terms. We can do this using:
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number | | | | | | | | | factor | factor | factor | factor | | | | | | | | | term | / | term | / | \ | / | \ | / | term | term |Similarly, terms and -s are combined in expressions:
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number | | | | | | | | | factor | factor | factor | factor | | | | | | | | | term | / | term | / | \ | / | \ | / | term | term | | | | | exp | / | \ | / | exp |and finally, the expression and the ; can be combined to make a line:
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number | | | | | | | | | factor | factor | factor | factor | | | | | | | | | term | / | term | / | \ | / | \ | / | term | term | | | | | exp | / | \ | / | exp / \ / line
2 * 3 - 4 * 1 ; | | | | | | | | number | number | number | number | (2) (3) (4) (1) | | | | | | | | factor | factor | factor | factor | (2) (3) (4) (1) | | | | | | | | term | / | term | / | (2) (4) \ | / | \ | / | term | term | (6=2*3) (4=4*1) | | | | exp | / | (6) \ | / | exp / (2=6-4) \ / lineSo the output (from the action for line) is:
result is 2Note that there is no value created for the line, as the corresponding action does not assign to $$.
Byacc will output a version of this if you turn on the full (yydebug=5) tracing:
.... look ahead at number `2' number <-- `2' factor term | .... look ahead at mul_div `*' | mul_div <-- `*' | | .... look ahead at number `3' | | number <-- `3' | | factor +-------+-------+ | term | .... look ahead at add_sub `-' exp | add_sub <-- `-' | | .... look ahead at number `4' | | number <-- `4' | | factor | | term | | | .... look ahead at mul_div `*' | | | mul_div <-- `*' | | | | .... look ahead at number `1' | | | | number <-- `1' | | | | factor | | +-------+-------+ | | | | | term | | | .... look ahead at ';' `;' +-------+-------+ | exp | ';' <-- `;' +-------+ | line .... look ahead at end-of-file `'Normally, we use an abstract parse tree to show the essentials of an expression:
2 3 4 1 ; \ / \ / | * * | \ / | - / \ / lineand this (but you needn't bother to include "line") is what I am expecting you to draw for the exercises, and (drawn on its side and, depending on how you look at it, upside-down) is what is output by the program you use for the accompanying Yacc practical:
1 * 4 - 3 * 2If we insert brackets around each operator node and its operands, we get the equivalent fully-bracketed expression:
((2*3)-(4*1))This is the most compact representation of the essence of the expression, but we can get lost if there are many nested brackets, and so it is usually more awkward to extend this style to represent the structure of complete programs. However, some programming languages, like LISP, do exactly that!