Programming)Languages)–

Lexical)and)Syntax)Analysis
Jongwoo&Lim
Introduc8on
• Language&implementa1on&systems&must&analyze&source&code,&
regardless&of&the&specific&implementa1on&approach.&
• Nearly&all&syntax&analysis&is&based&on&a&formal&descrip1on&of&the&
syntax&of&the&source&language&(BNF).&
D Compared&to&informal&syntax&descrip1ons,&BNF&descrip1ons&are&
• Clear&and&concise.&
• Used&as&the&direct&basis&for&the&syntax&analyzer.&
• Rela1vely&easy&to&maintain&due&to&their&modularity.

© 2009 Addison-Wesley.
Syntax)Analysis
• The&syntax&analysis&por1on&of&a&language&processor&nearly&always&
consists&of&two&parts:&
D A&lowDlevel&part&called&a&lexical)analyzer
(mathema1cally,&a&finite&automaton&based&on&a&regular&grammar)&
D A&highDlevel&part&called&a&syntax)analyzer,&or&parser&(mathema1cally,&
a&pushDdown&automaton&based&on&a&contextDfree&grammar,&or&BNF)&
• Why?&
D Simplicity:&less&complex&approaches&can&be&used&for&lexical&analysis;&
separa1ng&them&simplifies&the&parser&
D Efficiency:&separa1on&allows&op1miza1on&of&the&lexical&analyzer&
D Portability:&parts&of&the&lexical&analyzer&may&not&be&portable,&but&the&
parser&always&is&portable
© 2009 Addison-Wesley.
Syntax)Analysis)Example
1. E ! E add T
2. E ! T E Parse&tree

3. T ! T mul F T
4. T ! F F
5. F ! lp E rp E
6. F ! id | num
E
T T T
digit : [0-9] F F F
alpha : [a-zA-Z]
id : alpha(alpha|digit)* id mul lp id add num rp
num : digit+ Array&of&tokens
|(digit+ ‘.’ digit+)
var102 * (aa + 1024)
add : ‘+’
// add 1024 to aa first.
mul : ‘*’
lp : ‘(‘ Input&string
rp : ‘)’
Lexical)Analysis
• A&lexical&analyzer&is&a&paUern&matcher&for&character&strings.&
• A&lexical&analyzer&is&a&“frontDend”&for&the&parser.&
• Iden1fies&substrings&of&the&source&program&that&belong&together&D&
lexemes&
D Lexemes&match&a&character&paUern,&which&is&associated&with&a&lexical&
category&called&a&token.&
sum = a + b;
D sum&is&a&lexeme;&its&token&may&be&IDENT.&
D =&is&a&lexeme&and&its&token&may&be&ASSIGN_OP.&
D Skip&comments&and&blanks&outside&lexemes.&
D Put&userDdefined&names&into&the&symbol&table.&
D Detect&syntac1c&errors&in&tokens&(e.g.&0.0001.23,&2to3).
© 2009 Addison-Wesley.
Lexical)Analyzer
• The&lexical&analyzer&is&usually&a&func1on&that&is&called&by&the&
parser&when&it&needs&the&next&token.&
• Three&approaches&to&building&a&lexical&analyzer:&
D Write&a&formal&descrip1on&of&the&tokens&and&use&a&so]ware&tool&that&
constructs&tableDdriven&lexical&analyzers&given&such&a&descrip1on.&
D Design&a&state)diagram&that&describes&the&tokens&and&write&a&
program&that&implements&the&state&diagram.&
D Design&a&state&diagram&that&describes&the&tokens&and&handDconstruct&
a&tableDdriven&implementa1on&of&the&state&diagram.

© 2009 Addison-Wesley.
State)Diagram)Design
• State&transi1on&diagram:&
D A&directed&graph,&whose&nodes&are&state&names,&and&whose&
edges(arcs)&are&with&input&characters&that&cause&the&transi1on.&
D Mathema1cally,&a&finite&automaton&based&on&a&regular&grammar.&
D Example&of&regular&grammars:&wildcard&in&filename&matching.&
*.txt, test[0-9]+.doc, …

*.txt : .txt, b.txt, abcd.txt 12c4e.txt a_b_123.txt

but not a.pdf, abc.text, abc.txt.pdf .

test[0-9]+.doc : test0.doc, test1023.doc, test001.doc

but not test.doc, testabc.doc, test00a.doc .

© 2009 Addison-Wesley.
State)Diagram

© 2009 Addison-Wesley.
State)Diagram)Design
• State&transi1on&diagram&
D A&naïve&state&diagram&would&have&a&transi1on&from&every&state&on&
every&character&in&the&source&language&D&such&a&diagram&would&be&
very&large!&
D Group&characters&in&the&same&transi1on.&
• e.g.&LETTER for&all&52&upperD&and&lowerDcase&characters,
a&digit&class&DIGIT&for&all&digits.&
D Reserved&words&and&iden1fiers&can&be&recognized&together&(rather&
than&having&a&part&of&the&diagram&for&each&reserved&word).&
• Use&a&table&lookup&to&determine&whether&a&possible&iden1fier&is&in&
fact&a&reserved&word.

© 2009 Addison-Wesley.
Lexical)Analyzer
• Convenient&u1lity&subprograms:&
D getChar&D&gets&the&next&character&of&input,&puts&it&in&nextChar,&
determines&its&class&and&puts&the&class&in&charClass&.&
D addChar&D&puts&the&character&from&nextChar&into&the&place&the&
lexeme&is&being&accumulated,&lexeme&.&
D lookup&D&determines&whether&the&string&in&lexeme&is&a&reserved&word&
(returns&a&code).&
• Not&a&good&example!&
D Avoid&using&global&variables.&
D Func1on&names&do&not&show&there&meanings&clearly.&
D Complex&structure.

© 2009 Addison-Wesley.
 Chomsky)Hierarchy
• Type
Grammar to enter text
Languages Automaton Produc8on)rules

TypeD0 Recursively&enumerable Turing&machine &α&→&β&(no&restric1on)

LinearDbounded&nonDdeterminis1c&
TypeD1 ContextDsensi1ve &αAβ&→&αγβ
Turing&machine
NonDdeterminis1c&pushdown&
TypeD2 ContextDfree &A&→&γ
automaton
TypeD3 Regular Finite&state&automaton &A&→&a&and&A&→&aB
From&wikipedia
Regular)Language
• Formal&defini1on:&
D The&empty&language&Ø&is&a&regular&language.&
D For&each&a&∈&Σ,&the&singleton&language&{&a&}&is&a&regular&language.&
D If&A&and&B&are&regular&languages,&then&
• A∪B&(union,&OR),&
• AlB&(concatena1on),&and&
• A⋆&(Kleene&star)&are&regular&languages.&
D No&other&languages&over&Σ&are&regular.&

• Accepted&by&a&finite&state&machine.
Regular)Expressions
D Boolean&OR:&&‘gray’&or&‘grey’&&→&gray|grey&&
D Grouping:&&gr(a|e)y&
D Quan1fica1on:&&repe11on&(?,&*,&+),&& &e.g.&ab*c&&→&&ac,&abc,&abbc,&…&

POSIX&(extended)&regular&expressions
. &Matches&any&single&character&(many&applica1ons&exclude&newlines). a.c [a.c]
[ ] &Matches&a&single&character&that&is&contained&within&the&brackets. [abc] [a-z] [abcx-z]
[^ ] &Matches&a&single&character&that&is&not&contained&within&the&brackets. [^abc] [^a-z]
^ &Matches&the&star1ng&posi1on&within&the&string. ^abc
$ &Matches&the&ending&posi1on&of&the&string. abc$
( ) &Defines&a&marked&subexpression&(a&block&or&capturing&group). a(b|c)d
| &The&choice&(aka&alterna1on&or&set&union)&operator. abc|def
* &Matches&the&preceding&element&zero&or&more&1mes. ab*c [xyz]* (ab)*
? &Matches&the&preceding&element&zero&or&one&1me. ab? a.?
+ &Matches&the&preceding&element&one&or&more&1mes. ab+
{m,n} &Matches&the&preceding&element&at&least&m&and&not&more&than&n&1mes. a{3,5}
FiniteDstate)Automaton
• FiniteDstate&machine&
D It&is&in&only&one&state&at&a&1me&(the&current&state).&
D It&changes&state&by&a&triggering&event&or&condi1on&(transi1on).&
D Acceptors&(recognizers):&start&and&accept&(final)&state.&
D Determinis1c&vs.&nonDdeterminis1c.&
• Mul1ple&transi1ons&for&the&same&symbol.&
• Transi1ons&without&input&symbols&("εDmoves").

State&transi1on&diagrams 0 1
S1* S2 S1
S2 S1 S2

State/event&tables

0 1
p p p,q
q* D D
Regular)Expressions
a a b ε
ab : a* :
a

a-z a|b : ε
a
ε ε a+ :
a
^abc b
ε ε
ε
POSIX&(extended)&regular&expressions
. &Matches&any&single&character&(many&applica1ons&exclude&newlines). a.c [a.c]
[ ] &Matches&a&single&character&that&is&contained&within&the&brackets. [abc] [a-z] [abcx-z]
[^ ] &Matches&a&single&character&that&is&not&contained&within&the&brackets. [^abc] [^a-z]
^ &Matches&the&star1ng&posi1on&within&the&string. ^abc
$ &Matches&the&ending&posi1on&of&the&string. abc$
( ) &Defines&a&marked&subexpression&(a&block&or&capturing&group). a(b|c)d
| &The&choice&(aka&alterna1on&or&set&union)&operator. abc|def
* &Matches&the&preceding&element&zero&or&more&1mes. ab*c [xyz]* (ab)*
+ &Matches&the&preceding&element&one&or&more&1mes. ab+
Nondeterminis8c)FiniteDstate)Automaton
• Powerset&construc1on:&
D Conver1ng&a&nondeterminis1c&finiteDstate&automaton&(NFA)&to&a&
determinis1c&one&(DFA).&
D If&the&NFA&has&n&states,&the&resul1ng&DFA&may&have&2n&states.

ε 0 1
1 3 2 D
2 D D 2,4
3* 2 4 D
4* D 3 D

0 1
{1,2,3}* {2,4} {2,4}
{2,4}* {2,3} {2,4}
{2,3}* {4} {2,4}
{4}* {2,3} ø
ø ø ø
Nondeterminis8c)FiniteDstate)Automaton
• Powerset&construc1on:&
D Ini1al&state&of&the&resul1ng&DFA:&
• The&ini1al&state&of&NFA,&and&
the&states&reachable&by&εDmoves&from&the&ini1al&state.&
D For&each&state&in&the&DFA&whose&transi1on&is&unknown:&
• For&each&symbol,
find&the&states&in&NFA&a]er&the&transi1on&by&the&symbol,&and
all&the&states&reachable&by&εDmoves&from&those&states.&
• Repeat&un1l&no&such&states&in&the&DFA&exist.
Lex)/)Flex
• Lexical&analyzer&generator.&
%{
#include <stdio.h>
%}
...
digit [0-9]
letter [a-zA-Z]

%% /*** Rules section ***/

"var" { printf("VAR\n"); }
"while" { printf("WHILE\n"); }
{letter}({letter}|{digit})* { printf("ID: %s\n", yytext); }
{digit}+ { printf("Integer: %s\n", yytext); }
.|\n { /* Ignore all other characters. */ }

%% /*** C Code section ***/

int main(void) {
yylex();
return 0;
}
The)Parsing)Problem
• Goals&of&the&parser:&
D Given&an&input&program,&find&all&syntax&errors;
for&each,&produce&an&appropriate&diagnos1c&message&and&recover&
quickly.&
• Detect&as&many&errors&as&possible&during&a&single&analysis.&
D Produce&the&parse&tree,&or&at&least&a&trace&of&the&parse&tree,&for&the&
program.

© 2009 Addison-Wesley.
The)Parsing)Problem
• Two&categories&of&parsers&
D Top&down:&&produce&the&parse&tree,&beginning&at&the&root.&
• Order&is&that&of&a&le]most&deriva1on.&
• Traces&or&builds&the&parse&tree&in&preorder.&
D BoUom&up:&&produce&the&parse&tree,&beginning&at&the&leaves.&
• Order&is&that&of&the&reverse&of&a&rightmost&deriva1on.&

• Useful&parsers&look&only&one&token&ahead&in&the&input.
Nota1onal&conven1ons&in&the&chapter.
&Terminal&symbols Lowercase&leUers&at&the&beginning&of&alphabet. a,&b,&c,&…
NonDterminal&symbols Uppercase&leUers&at&the&beginning&of&alphabet. A,&B,&C,&…
Terminals&OR&nonDterminals Uppercase&leUers&at&the&end&of&alphabet. Z,&Y,&X,&W,&…
Strings&of&terminals Lowercase&leUers&at&the&end&of&alphabet. z,&y,&x,&w,&…
Mixed&strings Lowercase&Greek&leUers. α,&β,&γ,&δ,&…
© 2009 Addison-Wesley.
TopDdown)Parsers
• TopDdown&Parsers&
D Builds&a&parse&tree&in&preorder&(le]most&deriva1on).&
D Given&a&senten1al&form,&xAα,&and&the&ADrules,
& e.g.&&A&→&bB,&&A&→&cBb,&and&&A&→&a,
the&parser&must&choose&the&correct&ADrule&to&get&the&next&senten1al&
form&in&the&le]most&deriva1on,
& e.g.&&xbBα,&&xcBbα,&or&&xaα,
(using&only&the&first&token&produced&by&A).&
• The&most&common&topDdown&parsing&algorithms:&
D RecursiveDdescent&parser:&a&coded&implementa1on&of&BNF.&
D LL&parsers:&table&driven&implementa1on.&
• Le]DtoDright&scan,&and&a&Le]most&deriva1on&is&generated.
© 2009 Addison-Wesley.
BoNomDup)Parsers
• BoUomDup&parsers&
D Builds&a&parse&tree&from&leaves&toward&the&root&–
the&reverse&of&a&rightmost&deriva1on.&
D Given&a&right&senten1al&form,&α,&determine
what&substring&of&α&is&the&rightDhand&side&of&the&rule&(handle)
in&the&grammar&that&must&be&reduced
to&produce&the&previous&senten1al&form&in&the&right&deriva1on.
&&e.g.&&&S&→&aAc,&&A&→&aA&|&b,&&and
&&&&&&&&&&S&⇒&aAc&⇒&aaAc&⇒&aabc,
& then&&aabc&>>&aaAc&>>&aAc&>>&S.&
D The&most&common&boUomDup&parsers&are&in&the&LR&family.&
• Le]DtoDright&scan,&and&a&Rightmost&deriva1on&is&generated.

© 2009 Addison-Wesley.
The)Parsing)Problem
• The&Complexity&of&Parsing&
D Parsers&that&work&for&any&unambiguous&grammar&are&complex&and&
inefficient&–&O(n3),&where&n&is&the&length&of&the&input.&
D Compilers&use&parsers&that&only&work&for&a&subset&of&all&unambiguous&
grammars,&but&do&it&in&linear&1me&–&O(n).

© 2009 Addison-Wesley.
RecursiveDDescent)Parsing
• There&is&a&subprogram&for&each&nonterminal&in&the&grammar,&
which&can&parse&sentences&that&can&be&generated&by&that&
nonterminal.&
• EBNF&is&ideally&suited&for&being&the&basis&for&a&recursiveDdescent&
parser,&because&EBNF&minimizes&the&number&of&nonterminals.

© 2009 Addison-Wesley.
RecursiveDDescent)Parsing
• Assume&we&have&a&lexical&analyzer&named&lex,&which&puts&the&
next&token&code&in&nextToken.&
D Every&parsing&rou1ne&leaves&the&next&token&in&nextToken.&
• The&coding&process&when&there&is&only&one&RHS:&
D For&each&terminal&symbol&in&the&RHS,&compare&it&with&the&next&input&
token;&if&they&match,&con1nue,&else&there&is&an&error.&
D For&each&nonterminal&symbol&in&the&RHS,&call&its&associated&parsing&
subprogram.

© 2009 Addison-Wesley.
RecursiveDDescent)Parsing
• A&nonterminal&that&has&more&than&one&RHS&requires&an&ini1al&
process&to&determine&which&RHS&it&is&to&parse.&
D The&correct&RHS&is&chosen&on&the&basis&of&the&next&token&of&input&(the&
lookahead).&
D The&next&token&is&compared&with&the&first&token&that&can&be&
generated&by&each&RHS&un1l&a&match&is&found.&
D If&no&match&is&found,&it&is&a&syntax&error.

© 2009 Addison-Wesley.
RecursiveDDescent)Parsing
• A&grammar&for&simple&expressions:&

<expr> ! <term> {(+ | -) <term>}

<term> ! <factor> {(* | /) <factor>}
<factor> ! id | int_constant | ( <expr> )

© 2009 Addison-Wesley.
Recursive)Descent)Parsing
<expr> ! <term> {(+ | -) <term>}

/* Function expr
Parses strings in the language generated by the rule:
<expr> ! <term> {(+ | -) <term>}
*/

void expr() {
printf("Enter <expr>\n");
term(); // First term.

// As long as the next token is + or -, call lex() to get

// the next token and parse the next term.
while (nextToken == ADD_OP || nextToken == SUB_OP){
lex();
term();
}
// This routine does not detect errors.
printf("Exit <expr>\n");
}

© 2009 Addison-Wesley.
Recursive)Descent)Parsing
<term> ! <factor> {(* | /) <factor>}

/* Function term
Parses strings in the language generated by the rule:
<term> -> <factor> {(* | /) <factor>)
*/

void term() {
printf("Enter <term>\n");
factor(); // Parse the first factor.

// As long as the next token is * or /, call lex() to get

// next token and parse the next factor.
while (nextToken == MULT_OP || nextToken == DIV_OP) {
lex();
factor();
}
printf("Exit <term>\n");
}

© 2009 Addison-Wesley.
Recursive)Descent)Parsing
<factor> ! id | int_constant | ( <expr> )

/* Function factor
Parses strings in the language generated by the rule:
<factor> -> id | (<expr>)
*/

void factor() {
// Determine which RHS.
if (nextToken) == ID_CODE || nextToken == INT_CODE) {
// For the RHS id or int_constant, just call lex.
lex();
} else if (nextToken == LP_CODE) {
// If the RHS is (<expr>) – call lex to pass over ‘(’,
// call expr, and check for ‘)’.
lex();
expr();
if (nextToken == RP_CODE) lex();
else error();
} else {
error(); // Neither RHS matches.
}
}
© 2009 Addison-Wesley.
Recursive)Descent)Parsing void expr() {
printf("Enter <expr>\n");
term();
while (nextToken == ADD_OP ||
nextToken == SUB_OP){
<expr> lex();
term();
}
printf("Exit <expr>\n");
<term> }

void term() {
printf("Enter <term>\n");
<factor> <factor> factor();
while (nextToken == MULT_OP ||
nextToken == DIV_OP) {
lex();
factor();
<expr> }
printf("Exit <term>\n");
}

<term> <term> void factor() {

if (nextToken) == ID_CODE ||
nextToken == INT_CODE) {
lex();
<factor> <factor> } else if (nextToken == LP_CODE) {
lex();
expr();
if (nextToken == RP_CODE) lex();
else error();
( sum + 47 ) / total } else {
error();
}
}
© 2009 Addison-Wesley.
Recursive)Descent)Parsing
(sum + 47) / total

Next token is: 25 Next lexeme is ( Next token is: 24 Next lexeme is /
Enter <expr> Exit <factor>
Enter <term> Next token is: 11 Next lexeme is total
Enter <factor> Enter <factor>
Next token is: 11 Next lexeme is sum Next token is: -1 Next lexeme is EOF
Enter <expr> Exit <factor>
Exit <term>
Enter <term>
Exit <expr>
Enter <factor>
Next token is: 21 Next lexeme is +
Exit <factor>
Exit <term>
Next token is: 10 Next lexeme is 47
Enter <term>
Enter <factor>
Next token is: 26 Next lexeme is )
Exit <factor>
Exit <term>
Exit <expr>

© 2009 Addison-Wesley.
Recursive)Descent)Parsing
<if_stmt> ! if ( <bool_expr> ) <stmt> [else <stmt>]

void if_stmt() {
if (nextToken != IF_CODE) {
error();
} else {
lex();
if (nextToken != LEFT_PAREN) {
error();
} else {
lex();
bool_expr();
if (nextToken != RIGHT_PAREN) {
error();
} else {
lex();
stmt();
if (nextToken == ELSE_CODE) {
lex();
stmt();
}
}
}
}
}
© 2009 Addison-Wesley.
LL)Grammar)Class
• LL(k)&parser&
D LL&parser&that&requires&k&lookahead&tokens.&
D We&only&deal&with&LL(1)&parser&in&this&class.&

• Example&:&parsing&using&an&LL(1)&parser.&
Example: ( a + a ) 1. S ! F
2. S ! ( S + F )
token rule stack 3. F ! a
S, EOF
( ) a + EOF
( 2 (, S, +, F, ), EOF
( S, +, F, ), EOF S 2 - 1 - -
a 1 F, +, F, ), EOF F - - 3 - -
a 3 a, +, F, ), EOF
a +, F, ), EOF
+ F, ), EOF
a 3 a, ), EOF
a ), EOF
) EOF
© 2009 Addison-Wesley.
LeP)Recursion
• The&Le]&Recursion&Problem&
D If&a&grammar&has&leP)recursion,&either&direct&or&indirect,&
it&cannot&be&the&basis&for&a&topDdown&parser.&
D A&grammar&can&be&modified&to&remove&le]&recursion:
&&&For&each&nonterminal,&A,&
&&&Group&the&ADrules&as&&A&→&Aα1&|&Aα2&|...&|&Aαm&|&β1&|&β2&|...&|&βn&,
&&&&&&where&none&of&the&β’s&begins&with&𝐴.
&&&Replace&the&original&ADrules&with
& A&→&β1&A’&|&β2&A’&|&...&|&βn&A’
& A’&→&α1&A’&|&α2&A’&|&...&|&αm&A’&|&ε

© 2009 Addison-Wesley.
Disjointness
• The&other&characteris1c&of&grammars&that&disallows&topDdown&
parsing&is&the&lack&of&pairwise&disjointness.&
D The&inability&to&determine&the&correct&RHS&on&the&basis&of&one&token&
of&lookahead.&
D Defini1on&the&firstDset:&&FIRST(α)&=&{&c&|&α&⇒*&c&β&}
&&&&&If&α&⇒*&ε&,&ε&is&in&FIRST(𝛼).&

• Pairwise&Disjointness&Test:&
D For&each&nonterminal,&A,&that&has&more&than&one&RHS,
for&each&pair&of&rules,&A&→&αi&,&and&A&→&αj&,&&FIRST(αi)&∩&FIRST(αj)&=&∅&.
Examples:
& A&→&aB&|&bAb&|&Bb,&B&→&cB&|&d& &&&&FIRST&of&ADrules:&{a},&{b},&{c,d}
& A&→&aB&|&Bab,&B&→&aB&|&b& &&&&FIRST&of&ADrules:&{a},&{a,b}
© 2009 Addison-Wesley.
LeP)Factoring
• Le]&factoring&can&resolve&the&problem&
D Leave&the&common&parts&and&separate&the&rest&into&a&new&rule.&
D Example:
<var>&→&iden1fier&|&iden1fier&‘[’&<expression>&‘]’
can&be&wriUen&as
& <var>&→&iden1fier&<var2>
& <var2>&→&ε&|&‘[’&<expression>&‘]’
or
& <var>&→&iden1fier&[&‘[’&<expression>&‘]’&]
& & (the&outer&brackets&are&metaDsymbols&of&EBNF)

© 2009 Addison-Wesley.
First)Set
• Build&the&firstDset.&
D Given&a&grammar&with&the&rules&&A1&→&ω1&,&...&,&&An&→&ωn&,&
D Define&FIRST(X)&for&a&single&terminal&or&nonterminal&X:&
• X&is&a&terminal&‘a’:&&FIRST(X)&=&{a}.&
• X&is&‘ε’:&&FIRST(X)&=&{ε}.&
• X&is&a&nonterminal:&&for&every&rule&&X&→&B1&B2&...&Bm&,&
Put&&FIRST(B1)&−&{ε}&&into&&FIRST(X).&
If&all&&FIRST(Bj)&&contains&ε,&&1&≤&j&<&i,&&i&≤&m&,
& put&&FIRST(Bi)&−&{ε}&&into&&FIRST(X).&
If&all&FIRST(Bi)&contains&&𝜀&,&&1&≤&i&≤&m&,&put&&{ε}&&into&FIRST(X).

© 2009 Addison-Wesley.
First)Set
• Algorithm:&
D Given&a&grammar&with&the&rules&&A1&→&ω1&,&...&,&&An&→&ωn&,&
D Ini1alize&&FIRST(A)&←&{&},&&∀A.&
D Iterate&un1l&no&changes&in&all&&FIRST(A)&:&
• For&each&rule&A&→&X1&X2&...&Xm,&set&&k&=&1,&empty&=&true.&
• While&empty&==&true&&&&&&k&≤&m,&
Put&&FIRST(Xk)&−&{ε}&&into&&FIRST(A).&
empty&=&(&ε&∈&FIRST(Xk)&),&k&=&k&+&1.&
• If&&empty&==&true&,&put&&{ε}&&into&&FIRST(A).

© 2009 Addison-Wesley.
First)Set)Examples
S ! F E ! E + T | T E ! T E’
S ! ( S + F ) T ! T * F | F E’ ! + T E’ | ε
F ! a F ! ( E ) | id T ! F T’
T’ ! * F T’ | ε
F ! ( E ) | id
Itera1ons Itera1ons Itera1ons
1 2 1 2 3 1 2 3
S ( (, a E ∅ ∅ (, id E ∅ ∅ (, id
F a T ∅ (, id E’ +, ε
F (, id T ∅ (, id
T’ *, ε
FirstSet Algorithm
Initialize FIRST(A) ← {}, ∀A. F (, id
Iterate until no changes in all FIRST(A) :
For each rule A ! X1 X2 ... Xm,
Set k = 1, empty = true.
While empty == true && k ≤ m,
Put FIRST(Xk) − {ε} into FIRST(A).
k = k + 1, empty = (ε ∈ FIRST(Xk)).
If empty == true, put {ε} into FIRST(A).
© 2009 Addison-Wesley.
Follow)Set
• Follow&set&for&a&nonterminal&A:&
D Set&of&terminals&that&can&appear&at&the&immediately&right&of&A.
& e.g.&‘a’&is&in&FOLLOW(A)&if&B&⇒+&βAaγ.&
D If&A&can&be&at&the&rightmost&symbol,&$&(EOF)&is&in&FOLLOW(A).&
D ‘ε’&can&never&be&in&follow&sets.&

• Build&follow&sets&for&the&nonterminals&A.&
D If&A&is&the&start&state,&put&$&into&FOLLOW(A).&
D For&each&rule&B&→&αAβ,&put&FIRST(β)&−&{ε}&into&FOLLOW(A).&
D If&FIRST(β)&has&ε,&put&FOLLOW(B)&to&FOLLOW(A).&
D For&each&rule&C&→&γA,&put&FOLLOW(C)&to&FOLLOW(A).

© 2009 Addison-Wesley.
LL(1))Parser
• To&build&the&parsing&table,&
D For&each&rule&A&→&α,&
D For&each&terminal&‘a’&in&FIRST(α),&put&α&in&Table(A,&a).&
• If&ε&is&in&FIRST(α),&
For&each&terminal&‘a’&in&FOLLOW(A),&put&α&in&Table(A,&a).&
• The&grammar&is&not&LL(1)&if&and&only&if
there&is&more&than&one&entry&for&any&cell&in&the&table.

© 2009 Addison-Wesley.
LL(1))Parser
• Parsing&using&the&parsing&table.& 1. S ! F
Example: ( a + a ) 2. S ! ( S + F )
3. F ! a

token rule stack ( ) a + EOF

S, EOF S 2 - 1 - -
( 2 (, S, +, F, ), EOF F - - 3 - -
( S, +, F, ), EOF
a 1 F, +, F, ), EOF
a 3 a, +, F, ), EOF
a +, F, ), EOF
+ F, ), EOF
a 3 a, ), EOF
a ), EOF
) EOF

© 2009 Addison-Wesley.
LL(1))Parser
1. S ! F : FIRST(F) = { a } ( ) a + $
2. S ! (S+F): FIRST((S+F)) = { ( }
S 2 - 1 - -
3. F ! a : FIRST(a) = { a }
F - - 3 - -

• Try&to&parse&‘a’,&‘(a + a)’,&and&‘((a + a) + a)’.

Build&LL(1)&Parsing&Table
For&each&rule&A→α,&
&&&&For&each&terminal&‘a’&in&FIRST(α),&put&α&in&Table(A,&a).
&&&&&&&&If&ε&is&in&FIRST(α),
&&&&&&&&For&each&terminal&‘a’&in&FOLLOW(A),&put&α&in&Table(A,&a).

© 2009 Addison-Wesley.
LL(1))Parser
1. S ! F S : FIRST(F S) = { a } a + $
2. S ! + S : FIRST(+ S) = { + }
S 1 2 3
3. S ! ε : FIRST(ε) = { ε }
F 4 - -
FOLLOW(S) = { $ }
4. F ! a : FIRST(a) = { a }

• Try&to&parse&‘a’,&‘a + a’,&and&‘a + a + a’.

Build&LL(1)&Parsing&Table
For&each&rule&A→α,&
&&&&For&each&terminal&‘a’&in&FIRST(α),&put&α&in&Table(A,&a).
&&&&&&&&If&ε&is&in&FIRST(α),
&&&&&&&&For&each&terminal&‘a’&in&FOLLOW(A),&put&α&in&Table(A,&a).

© 2009 Addison-Wesley.
LL(1))Parser
1. A ! aB : FIRST(aB) = { a } a b c d $
2. A ! bAb : FIRST(bAb) = { b }
A 1 2 3 3 -
3. A ! Bb : FIRST(Bb) = { c, d }
B - - 4 5 -
4. B ! cB : FIRST(cB) = { c }
5. B ! d : FIRST(d) = { d }

• Try&to&parse&‘accd’,&‘badb’,&and&‘bbcdbbb’.

Build&LL(1)&Parsing&Table
For&each&rule&A→α,&
&&&&For&each&terminal&‘a’&in&FIRST(α),&put&α&in&Table(A,&a).
&&&&&&&&If&ε&is&in&FIRST(α),
&&&&&&&&For&each&terminal&‘a’&in&FOLLOW(A),&put&α&in&Table(A,&a).

© 2009 Addison-Wesley.
LL(1))Parser
1. A ! Ba : FIRST(Ba) = { b, c } a b c d $
2. A ! CB : FIRST(CB) = { b, c, d }
A - 1,2 1,2 2 -
3. B ! bc : FIRST(bc) = { b }
B - 3 4 - -
4. B ! cA : FIRST(cA) = { c }
C - 6 6 5 -
5. C ! d : FIRST(d) = { d }
6. C ! ε : FIRST(ε) = { ε }
FOLLOW(C) = { b, c }

• Not&an&LL(1)&grammar.

Build&LL(1)&Parsing&Table
For&each&rule&A→α,&
&&&&For&each&terminal&‘a’&in&FIRST(α),&put&α&in&Table(A,&a).
&&&&&&&&If&ε&is&in&FIRST(α),
&&&&&&&&For&each&terminal&‘a’&in&FOLLOW(A),&put&α&in&Table(A,&a).

© 2009 Addison-Wesley.
BoNomDup)Parsing
• The&parsing&problem&is&finding&the&correct&RHS&in&a&rightD
senten1al&form&to&reduce&to&get&the&previous&rightDsenten1al&
form&in&the&deriva1on.&
D BoUomDup&parsing:&&use&rightmost&deriva1on.&

id + id * id id + id + id E ! E + T | T
E ⇒ E + T E ⇒ E + T T ! T * F | F
⇒ E + T * F ⇒ E + F F ! ( E ) | id
⇒ E + T * id ⇒ E + id
⇒ E + F * id ⇒ E + T + id
⇒ E + id * id ⇒ E + F + id
⇒ T + id * id ⇒ E + id + id
⇒ F + id * id ⇒ T + id + id
⇒ id + id * id ⇒ F + id + id
⇒ id + id + id
© 2009 Addison-Wesley.
BoNomDup)Parsing
• Intui1on&about&handles.&
D Defini1on:&&β&is&the&handle&of&the&right&senten1al&form&γ=αβw
&&&&if&and&only&if&&S&⇒*rm&αAw&⇒rm&αβw.&
D Defini1on:&&β&is&a&phrase&of&the&right&senten1al&form&γ
&&&&if&and&only&if&&S&⇒*&γ=α1Aα2&⇒+&α1βα2&
D Defini1on:&&β&is&a&simple)phrase&of&the&right&senten1al&form&γ

&&&&if&and&only&if&&S&⇒*&γ=α1Aα2&⇒&α1βα2.&
• #phrases&=&#internal&nodes&in&parse&tree.&
• A&simple&phrase&is&always
an&RHS&in&the&grammar.

© 2009 Addison-Wesley.
BoNomDup)Parsing
• Intui1on&about&handles:&
D The&handle&of&any&rightmost&senten1al&form&is&its&le]most&simple&
phrase.&
D Given&a&parse&tree,&it&is&now&easy&to&find&the&handle.&
D Parsing&can&be&thought&of&as&handle&pruning.&

E ⇒ E + T E E ! E + T | T
⇒ E + T * F T ! T * F | F
E T
⇒ E + T * id F ! ( E ) | id
⇒ E + F * id T T
⇒ E + id * id
⇒ T + id * id F F F
⇒ F + id * id
⇒ id + id * id id + id * id

© 2009 Addison-Wesley.
BoNomDup)Parsing
• Intui1on&about&handles:&
D The&handle&of&any&rightmost&senten1al&form&is&its&le]most&simple&
phrase.&
D Given&a&parse&tree,&it&is&now&easy&to&find&the&handle.&
D Parsing&can&be&thought&of&as&handle&pruning.&

E ⇒ E + T E E ! E + T | T
⇒ E + F T ! T * F | F
E
⇒ E + id F ! ( E ) | id
⇒ E + T + id E
⇒ E + F + id T T T
⇒ E + id + id
⇒ T + id + id F F F
⇒ F + id + id
id + id + id
⇒ id + id + id
© 2009 Addison-Wesley.
ShiPDReduce)Algorithms
• Shi]DReduce&Algorithms:&
D ShiP&ac1on&moves&the&next&token&onto&the&parse&stack.&
D Reduce&ac1on&replaces&the&handle&on&top&of&the&parse&stack&with&its&
corresponding&LHS.&
D Pushdown&automaton&(PDA).

© 2009 Addison-Wesley.
LR)Parsers
• Advantages&of&LR&parsers:&
D They&will&work&for&nearly&all&grammars&that&describe&programming&
languages.&
D They&work&on&a&larger&class&of&grammars&than&other&boUomDup&
algorithms,&but&are&as&efficient&as&any&other&boUomDup&parser.&
D They&can&detect&syntax&errors&as&soon&as&it&is&possible.&
D The&LR&class&of&grammars&is&a&superset&of&the&&class&parsable&by&LL&
parsers.&
• Disadvantage&of&LR&parsing:&
D The&parsing&table&is&hard&to&produce&by&hand.&
• Several&programs&available&for&this&purpose.

© 2009 Addison-Wesley.
LR)Parsers
• Knuth’s&insight:&
D A&boUomDup&parser&could&use&the&en1re&history&of&the&parse,&up&to&
the&current&point,&to&make&parsing&decisions.&
D There&were&only&a&finite&and&rela1vely&small&number&of&different&
parse&situa1ons&that&could&have&occurred,&so&the&history&could&be&
stored&in&a&parser&state,&on&the&parse&stack.&
D An&LR&configura1on&stores&the&state&of&an&LR&parser
& (S0&X1&S1&X2&…&Xm&Sm,&ai&ai+1&…&an&$)&
D Sk&:&state&symbols,&Xk&:&grammar&symbols.

© 2009 Addison-Wesley.
BoNomDup)Parsing
• An&LR&configura1on&stores&the&state&of&an&LR&parser
& (S0&X1&S1&X2&…&Xm&Sm,&ai&ai+1&…&an&$)

© 2009 Addison-Wesley.
BoNomDup)Parsing
• LR&parsers&are&table&driven,&where&the&table&has&two&
components,&an&ACTION&table&and&a&GOTO&table.&
D The&ACTION&table&specifies&the&ac1on&of&the&parser,&given&the&parser&
state&and&the&next&token.&
• Rows&are&state&names;&columns&are&terminals.&
• R&for&reduce&and&S&for&shi].&
D The&GOTO&table&specifies&which&state&to&put&on&top&of&the&parse&stack&
a]er&a&reduc1on&ac1on&is&done.&
• Rows&are&state&names;&columns&are&nonterminals.&

• A&parser&table&can&be&generated&from&a&given&grammar&with&a&
tool,&e.g.,&yacc

© 2009 Addison-Wesley.
LR)Parsing)Table
1. E ! E + T
2. E ! T
3. T ! T * F
4. T ! F
5. F ! ( E )
6. F ! id

(S0&a1&a2&…&an&$)

© 2009 Addison-Wesley.
BoNomDup)Parsing
• Ini1al&configura1on:&&(S0,&a1&a2&…&an&$)&
D Parser&ac1ons:
& (S0&X1&S1&X2&S2&…&Xm&Sm,&ai&ai+1&…&an&$)&
D If&ACTION[Sm,&ai]&=&Shi]&S,&the&next&configura1on&is:
& (S0&X1&S1&X2&S2&…&Xm&Sm&ai&S,&ai+1&ai+2&…&an&$)&
D If&ACTION[Sm,&ai]&=&Reduce&A→β&and&S&=&GOTO[SmDr,&A],
where&r&=&the&length&of&β,&the&next&configura1on&is
& (S0&X1&S1&X2&S2&…&XmDr&SmDr&A&S,&ai&ai+1&…&an&$)&
D If&ACTION[Sm,&ai]&=&Accept,&the&parse&is&complete&and&no&errors&were&
found.&
D If&ACTION[Sm,&ai]&=&Error,&the&parser&calls&an&errorDhandling&rou1ne.

© 2009 Addison-Wesley.
LR)Parsing)Example
1. E ! E + T
2. E ! T
3. T ! T * F
4. T ! F
5. F ! ( E )
6. F ! id
Stack Input Action
Action Goto 0 id + id * id $ S5
id + * ( ) $ E T F 0 id 5 + id * id $ R6 (G[0,F])
0 S5 S4 1 2 3 0 F 3 + id * id $ R4 (G[0,T])
1 S6 ** 0 T 2 + id * id $ R2 (G[0,E])
2 R2 S7 R2 R2 0 E 1 + id * id $ S6
3 R4 R4 R4 R4 0 E 1 + 6 id * id $ S5
4 S5 S4 8 2 3 0 E 1 + 6 id 5 * id $ R6 (G[6,F])
5 R6 R6 R6 R6 0 E 1 + 6 F 3 * id $ R4 (G[6,T])
6 S5 S4 9 3 0 E 1 + 6 T 9 * id $ S7
7 S5 S4 10 0 E 1 + 6 T 9 * 7 id $ S5
8 S6 S11 0 E 1 + 6 T 9 * 7 id 5 $ R6 (G[7,F])
9 R1 S7 R1 R1 0 E 1 + 6 T 9 * 7 F 10 $ R3 (G[6,T])
10 R3 R3 R3 R3 0 E 1 + 6 T 9 $ R1 (G[0,E])
11 R5 R5 R5 R5 0 E 1 $ Accept
© 2009 Addison-Wesley.
LR)Parsing)Example
1. E ! E + T
2. E ! T
3. T ! T * F
4. T ! F
5. F ! ( E )
6. F ! id Stack Input Action
0 id + id + id $ S5
Action Goto
0 id 5 + id + id $ R6 (G[0,F])
id + * ( ) $ E T F
0 F 3 + id + id $ R4 (G[0,T])
0 S5 S4 1 2 3
0 T 2 + id + id $ R2 (G[0,E])
1 S6 **
0 E 1 + id + id $ S6
2 R2 S7 R2 R2
0 E 1 + 6 id + id $ S5
3 R4 R4 R4 R4 0 E 1 + 6 id 5 + id $ R6 (G[6,F])
4 S5 S4 8 2 3 0 E 1 + 6 F 3 + id $ R4 (G[6,T])
5 R6 R6 R6 R6 0 E 1 + 6 T 9 + id $ R1 (G[0,E])
6 S5 S4 9 3 0 E 1 + id $ S6
7 S5 S4 10 0 E 1 + 6 id $ S5
8 S6 S11 0 E 1 + 6 id 5 $ R6 (G[6,F])
9 R1 S7 R1 R1 0 E 1 + 6 F 3 $ R4 (G[6,T])
10 R3 R3 R3 R3 0 E 1 + 6 T 9 $ R1 (G[0,E])
11 R5 R5 R5 R5 0 E 1 $ Accept
LR)Parsing)
Example
1. E ! E + T
2. E ! T
3. T ! T * F
Stack Input Action
4. T ! F
5. F ! ( E ) 0 id * ( id + S5
id ) $
6. F ! id 0 id 5 * ( id + id ) $ R6 (G[0,F])
0 F 3 * ( id + id ) $ R4 (G[0,T])
Action Goto
0 T 2 * ( id + id ) $ S7
id + * ( ) $ E T F 0 T 2 * 7 ( id + id ) $ S4
0 S5 S4 1 2 3 0 T 2 * 7 ( 4 id + id ) $ S5
1 S6 ** 0 T 2 * 7 ( 4 id 5 + id ) $ R6 (G[4,F])
2 R2 S7 R2 R2 0 T 2 * 7 ( 4 F 3 + id ) $ R4 (G[4,T])
0 T 2 * 7 ( 4 T 2 + id ) $ R1 (G[0,E])
3 R4 R4 R4 R4
0 T 2 * 7 ( 4 E 1 + id ) $ S6
4 S5 S4 8 2 3
0 T 2 * 7 ( 4 E 1 + 6 id ) $ S5
5 R6 R6 R6 R6 0 T 2 * 7 ( 4 E 1 + 6 ) $ R6 (G[6,F])
6 S5 S4 9 3 idT52 *
0 7 ( 4 E 1 + 6 ) $ R4 (G[6,T])
F
0 3
T 2 * 7 ( 4 E 1 + 6
7 S5 S4 10 ) $ R1 (G[4,E])
T
8 S6 S11 0 9
T 2 * 7 ( 4 E 8 ) $ S11
0 T 2 * 7 ( 4 E 8 ) $ R5 (G[7,F])
9 R1 S7 R1 R1 11
0 T 2 * 7 F 10 $ R3 (G[0,T])
10 R3 R3 R3 R3
0 T 2 $ R2 (G[0,E])
11 R5 R5 R5 R5 0 E 1 $ Accept
Build)the)LR)Parsing)Table
• Algorithm&
D Find&the&follow&sets&of&all&nonDterminals.&
D Add&a&dummy&rule&S&→&A$,&(A&is&the&start&symbol),&and&put&a&dot&(.)&in&
front&of&A.&
D Whenever&the&dot&is&in&front&of&a&nonDterminal&A&→&α.Bβ,&
add&all&rules&of&B&with&a&dot&B&→&.γ&to&the&state.&
D Move&the&dot&over&one&symbol&X&in&the&state&s,&A&→&α.Xβ&⇒&A&→&αX.β
and&find&the&corresponding&state&s’&(or&make&a&new&state&if&not&exist).&
• If&X&is&a&terminal,&add&Shi]&s’&ac1on&to&Ac1on(s,X).&
• If&X&is&a&nonDterminal,&add&s’&to&Goto(s,X).&
• If&the&dot&reaches&the&end&of&a&rule&A&→&α,&put&Reduce&ac1on&to&
Ac1on(s,a)&for&each&element&a&in&the&follow&set&of&A.
 [1] [6]
S→E·$ E→E+·T
[9]
E→E·+T T→·T*F
LR)Parsing)Table T→·F
E→E+T·
T→T·*F
[2] F→·(E)
E→T· F → · id
1. E ! E + T [0] T→T·*F
2. E ! T S→·E$
E→·E+T [7]
3. T ! T * F [3]
E→·T T→T*·F [10]
4. T ! F T→F·
5. F ! ( E ) T→·T*F F→·(E) T→T*F·
6. F ! id T→·F F → · id
[4]
F→·(E) F→(·E)
F → · id E→·E+T [8]
[11]
E→·T F→(E·)
Action Goto F→(E)·
T→·T*F E→E·+T
id + * ( ) $ E T F
0 S5 S4 1 2 3 T→·F
1 S6 ** F→·(E)
F → · id
2 R2 S7 R2 R2
3 R4 R4 R4 R4
[5]
4 S5 S4 8 2 3 F → id ·
5 R6 R6 R6 R6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11 • Put&a&dot&at&the&beginning&of&the&start&rule.&
9 R1 S7 R1 R1 • Move&the&dot&over&the&next&symbol,
10 R3 R3 R3 R3
and&expand.
11 R5 R5 R5 R5
Summary
• Syntax&analysis&is&a&common&part&of&language&implementa1on&
• A&lexical&analyzer&is&a&paUern&matcher&that&isolates&smallDscale&
parts&of&a&program&
D Detects&syntax&errors&
D Produces&a&parse&tree&

• A&recursiveDdescent&parser&is&an&LL&parser&
D EBNF&
• Parsing&problem&for&boUomDup&parsers:&find&the&substring&of&
current&senten1al&form&
• The&LR&family&of&shi]Dreduce&parsers&is&the&most&common&
boUomDup&parsing&approach
© 2009 Addison-Wesley.
Calculator)LR)Parser
Grammar
<statement> ! <command> | <expr> | id | id ‘=‘ <expr>
<command> ! ‘list’ | ‘clear’ | ‘exit’ | ‘quit’
<expr> ! <expr> ‘+’ <term> | <expr> ‘-‘ <term> | <term>
<term> ! <term> ‘*’ <factor> | <term> ‘/’ <factor> | <factor>
<factor> ! <unary_op> <base> <exponent>
<unary_op> ! ‘+’ | ‘-‘ | ε
<base> ! ‘(‘ <expr> ‘)’ | id | number
<exponent> ! ‘^’ <factor> | ε

© 2009 Addison-Wesley.
Calculator)LR)Parser
Modified Grammar Modified Grammar
<start> ! <statement> $ 1. A ! S $
<statement> ! command 2. S ! cmd
<statement> ! id ‘=‘ <expr> 3. S ! id = E
<statement> ! <expr> 4. S ! E
<expr> ! <expr> ‘+’ <term> 5. E ! E + T
<expr> ! <expr> ‘-‘ <term> 6. E ! E - T
<expr> ! <term> 7. E ! T
<term> ! <term> ‘*’ <factor> 8. T ! T * F
<term> ! <term> ‘/’ <factor> 9. T ! T / F
<term> ! <factor> 10. T ! F
<factor> ! <base> 11. F ! B
<factor> ! <base> ‘^’ <factor> 12. F ! B ^ F
<factor> ! ‘+’ <base> 13. F ! + B
<factor> ! ‘+’ <base> ‘^’ <factor> 14. F ! + B ^ F
<factor> ! ‘-’ <base> 15. F ! - B
<factor> ! ‘-’ <base> ‘^’ <factor> 16. F ! - B ^ F
<base> ! id 17. B ! id
<base> ! number 18. B ! num
<base> ! ‘(‘ <expr> ‘)’ 19. B ! ( E )
Modified Grammar [0] [4] [11] [13] [14] [20] [28]
A→S$ A→.S$ G1 S→E. R3 B→(.E) G21 E→E+.T G23 E→E-.T G24 B → id . R16 F→+B^.F G31
1. S → cmd S → . cmd S2 E→E.+T S13 E→.E+T G21 T→.T*F G23 T→.T*F G5 F→.B G7
2. S → id = E S → . id = E S3 E→E.-T S14 E→.E-T G21 T→.T/F G23 T→.T/F G5 [21] F→.B^F G7
3. S→E S→.E E→.T T→.F T→.F B→(E.) F→.+B
G4 G5 G6 G6 S30 S8
4. E→E+T E→.E+T T→.T*F F→.B F→.B E→E.+T F→.+B^F
5. E→E-T G4 [5] G5 G7 G7 S13 S8

6. E→T E→.E–T G4 E→T. T→.T/F G5 F→.B^F G7 F→.B^F G7 E→E.-T S14 F→.-B S9

R6
7. T→T*F E→.T G5 T→T.*F T→.F G6 F→.+B S8 F→.+B S8 F→.-B^F S9
S15
8. T→T/F T→.T*F G5 T→T./F F→.B G7 F→.+B^F S8 F→.+B^F S8 [22] B → . id S20
S16
9. T→F T→.T/F G5 F→.B^F G7 F→.-B S9 F→.-B S9 S → id = E . R2 B → . num S10
10. F → B T→.F F→.+B F→.-B^F F→.-B^F E→E.+T B→.(E)
G6 S8 S9 S9 S13 S11
11. F → B ^ F F→.B [6] F→.+B^F B → . id B → . id
G7 S8 S20 S20 E→E.-T
12. F → + B T→F. S14

13. F → + B ^ F F→.B^F G7
R9 F→.-B S9 B → . num S10 B → . num S10 [29]
14. F → - B F→.+B F→.-B^F B→.(E) B→.(E) F→-B^.F
S8 S9 S11 S11 [23] G32
15. F → - B ^ F F→.+B^F S8
[7] B → . id S20 E→E+T. F→.B G7
R4
16. B → id F→.–B F→B. B → . num [15] [16] F→.B^F
S9 R10 S10 T→T.*F G7
17. B → num F→B.^F T→T*.F G25 T→T/.F G26
S15
F→.+B
F→.-B^F S9 S17 B→.(E) S11 T→T./F S8
18. B → ( E ) F→.B F→.B S16
B → . id S3
G7 G7 F→.+B^F S8
[12] F→.B^F F→.B^F
B → . num [8]
G7 G7 F→.-B S9
S10 S → id = . E G22 F→.+B F→.+B [24]
B→.(E) F→+.B S8 S8 F→.-B^F S9
S11 G18 E→.E+T G22 F→.+B^F F→.+B^F E→E–T. R5
[1] F→+.B^F S8 S8 B → . id S20
G18 E→.E-T G22 F→.-B F→.-B T→T.*F S15
A→S.$ B → . id S9 S9 B → . num S10
** S20 E→.T G5 F→.-B^F F→.-B^F T→T./F S16
B → . num S9 S9 B→.(E) S11
S10 T→.T*F G5 B → . id S20 B → . id S20
[2] B→.(E) S11 T→.T/F G5 B → . num B → . num
S → cmd .
S10 S10 [25] [30]
R1 T→.F G6 B→.(E) S11 B→.(E) S11 T→T*F. B→(E).
R7 R18
[9] F→.B G7
[3] F→-.B G19 F→.B^F [17]
G7 [18] [26] [31]
S → id . = E S12 F→-.B^F F→.+B F→B^.F
G19 S8 G27 F→+B. R12 T→T/F. F→+B^F.
B → id . B → . id F→.+B^F F→.B
R8 R13
R16 S20 S8 G7 F→+B.^F S28
B → . num S10 F→.-B S9 F→.B^F G7
B→.(E) F→.-B^F [27] [32]
S11 S9 F→.+B S8
[19] F→B^F. R15 F→-B^F. R15
B → . id S20 F→.+B^F S8
F→-B. R14
[10] B → . num F→.-B
S10 S9 F→-B.^F R29
B → num . R17 B→.(E) S11 F→.-B^F S9
B → . id S20
B → . num S10
B→.(E) S11
 Action Goto
id num cmd = + - * / ^ ( ) $ S E T F B
0 S3 S10 S2 S8 S9 1 4 5 6 7
1 **
2 R1
3 S12 R16 R16 R16 R16 R16 R16 R16
4 S13 S14 R3
5 R6 R6 S15 S16 R6 R6
6 R9 R9 R9 R9 R9 R9
7 R10 R10 R10 R10 S17 R10 R10
8 S20 S10 S11 18
9 S20 S10 S11 19
10 R17 R17 R17 R17 R17 R17 R17
11 S20 S10 S8 S9 S11 21 5 6 7
12 S20 S10 S8 S9 S11 22 5 6 7
13 S20 S10 S8 S9 S11 23 6 7
14 S20 S10 S8 S9 S11 24 6 7
15 S20 S10 S8 S9 S11 25 7
16 S20 S10 S8 S9 S11 26 7
17 S20 S10 S8 S9 S11 27 7
18 R12 R12 R12 R12 S28 R12 R12
19 R14 R14 R14 R14 S29 R14 R14
20 R16 R16 R16 R16 R16 R16 R16
21 S13 S14 S30
22 S13 S14 R2
23 R4 R4 S15 S16 R4 R4
24 R5 R5 S15 S16 R5 R5
25 R7 R7 R7 R7 R7 R7
26 R8 R8 R8 R8 R8 R8
27 R15 R15 R15 R15 R15 R15
28 S20 S10 S8 S9 S11 31 7
29 S20 S10 S8 S9 S11 32 7
30 R18 R18 R18 R18 R18 R18 R18
31 R13 R13 R13 R13 R13 R13
32 R15 R15 R15 R15 R15 R15