Difference between revisions of "Top-Down Parsing/Exercise 3"

From Wiki**3

< Top-Down Parsing
(New page: = Problem = Consider the following grammar, where '''<tt>F</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols: O -> a G -> F c | O c d | (eps) ...)
 
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{TOCright}}
 
= Problem =
 
= Problem =
  
−
Consider the following grammar, where '''<tt>F</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:
+
Consider the following grammar, where '''<tt>G</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:
  
 
  O -> a
 
  O -> a
Line 14: Line 15:
  
 
Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''
 
Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''
−
 
+
<!--
−
There are two ways of handling the mutual recursion: either expand F in G or G in F.
+
There are two ways of handling the mutual recursion: either expanding F in G or G in F.
  
 
== Expanding G in F ==
 
== Expanding G in F ==
Line 43: Line 44:
 
Factor F prefixes and expand it in G:
 
Factor F prefixes and expand it in G:
  
−
  G -> a c F'' c | b F' c | a c d | (eps)
+
  G -> a c F" c | b F' c | a c d | (eps)
−
  F -> a c F'' | b F'
+
  F -> a c F" | b F'
 
  F' -> c b F' | (eps)
 
  F' -> c b F' | (eps)
−
  F'' -> d b F' | F e F'
+
  F" -> d b F' | F e F'
  
 
Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases:
 
Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases:
  
 
  G -> a c G' | b F' c | (eps)
 
  G -> a c G' | b F' c | (eps)
−
  G' -> F'' c | d
+
  G' -> F" c | d
 
  F' -> c b F' | (eps)
 
  F' -> c b F' | (eps)
−
  F'' -> d b F' | a c F'' e F' | b F' e F'
+
  F" -> d b F' | a c F" e F' | b F' e F'
  
 
F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.
 
F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.
  
 
  G -> a c G' | b F' c | (eps)
 
  G -> a c G' | b F' c | (eps)
−
  G' -> d b F' c | a c F'' e F' c | b F' e F' c | d
+
  G' -> d b F' c | a c F" e F' c | b F' e F' c | d
 
  F' -> c b F' | (eps)
 
  F' -> c b F' | (eps)
−
  F'' -> d b F' | a c F'' e F' | b F' e F'
+
  F" -> d b F' | a c F" e F' | b F' e F'
  
 
Factoring prefixes in G', we get to the final version:
 
Factoring prefixes in G', we get to the final version:
  
 
  G -> a c G' | b F' c | (eps)
 
  G -> a c G' | b F' c | (eps)
−
  G' -> d G'' | a c F'' e F' c | b F' e F' c
+
  G' -> d G" | a c F" e F' c | b F' e F' c
−
  G'' -> b F' c | (eps)
+
  G" -> b F' c | (eps)
 
  F' -> c b F' | (eps)
 
  F' -> c b F' | (eps)
−
  F'' -> d b F' | a c F'' e F' | b F' e F'
+
  F" -> d b F' | a c F" e F' | b F' e F'
 +
-->
 +
=== Elimination of Mutual Recursion: Expanding F in G ===
 +
 
 +
Initial grammar:
 +
 
 +
O -> a
 +
G -> F c | O c d | (eps)
 +
F -> G b | O c F e
 +
 
 +
Eliminating the singularity (O->a):
 +
 
 +
G -> F c | a c d | (eps)
 +
F -> G b | a c F e
 +
 
 +
Expanding F in G:
 +
 
 +
G -> G b c | a c F e c | a c d | (eps)
 +
F -> G b | a c F e
 +
 
 +
Eliminating left recursion in G:
 +
 
 +
G -> a c F e c G' | a c d G' | G'
 +
G' -> b c G' | (eps)
 +
F -> G b | a c F e
 +
 
 +
Factoring G prefixes:
 +
 
 +
G -> a c G" | b c G' | (eps)
 +
G' -> b c G' | (eps)
 +
G" -> F e c G' | d G'
 +
F -> a c G" b | b c G' b | b | a c F e
 +
 
 +
Factoring F prefixes:
 +
 
 +
G -> a c G" | b c G' | (eps)
 +
G' -> b c G' | (eps)
 +
G" -> F e c G' | d G'
 +
F -> a c F' | b F"
 +
F' -> G" b | F e
 +
F" -> c G' b | (eps)
 +
 
 +
Eliminating non-terminal left corners (note that F becomes unreachable):
 +
 
 +
G -> a c G" | b c G' | (eps)
 +
G' -> b c G' | (eps)
 +
G" -> a c F' e c G' | b F" e c G' | d G'
 +
F' -> a c F' e c G' b | b F" e c G' b | d G' b | a c F' e | b F" e
 +
F" -> c G' b | (eps)
 +
 
 +
Factoring F' prefixes, we get to the final version:
 +
 
 +
G -> a c G" | b c G' | (eps)
 +
G' -> b c G' | (eps)
 +
G" -> a c F' e c G' | b F" e c G' | d G'
 +
F' -> a c F' e F" | b F" e F" | d G' b
 +
F" -> c G' b | (eps)
 +
 
 +
=== FIRST & FOLLOW sets ===
 +
 
 +
FIRST(G)  = { a, b, (eps) }              FOLLOW(G)  = { $ }
 +
FIRST(G') = { b, (eps) }                  FOLLOW(G') = { $, b }
 +
FIRST(G") = { a, b, d }                  FOLLOW(G") = { $ }
 +
FIRST(F') = { a, b, d }                  FOLLOW(F') = { e }
 +
FIRST(F") = { c, (eps) }                  FOLLOW(F") = { e }
 +
 
  
−
[[category:Compilers]]
+
[[category:Compiladores]]
−
[[category:Teaching]]
+
[[category:Ensino]]

Latest revision as of 16:40, 6 April 2015

Problem

Consider the following grammar, where G is the initial symbol and {a,b,c,d,e} is the set of terminal symbols: 

O -> a
G -> F c | O c d | (eps)
F -> G b | O c F e
  1. Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.
  2. Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.
  3. Show the analysis table (stack, input, and actions) for the parsing process of the acbec input sequence.

Solution

Something to keep in mind at all times: never eliminate the rules corresponding to the initial symbol

Elimination of Mutual Recursion: Expanding F in G

Initial grammar: 

O -> a 
G -> F c | O c d | (eps)
F -> G b | O c F e

Eliminating the singularity (O->a): 

G -> F c | a c d | (eps)
F -> G b | a c F e

Expanding F in G: 

G -> G b c | a c F e c | a c d | (eps)
F -> G b | a c F e

Eliminating left recursion in G: 

G -> a c F e c G' | a c d G' | G'
G' -> b c G' | (eps)
F -> G b | a c F e

Factoring G prefixes: 

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> F e c G' | d G'
F -> a c G" b | b c G' b | b | a c F e

Factoring F prefixes: 

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> F e c G' | d G'
F -> a c F' | b F"
F' -> G" b | F e
F" -> c G' b | (eps)

Eliminating non-terminal left corners (note that F becomes unreachable): 

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> a c F' e c G' | b F" e c G' | d G'
F' -> a c F' e c G' b | b F" e c G' b | d G' b | a c F' e | b F" e
F" -> c G' b | (eps)

Factoring F' prefixes, we get to the final version: 

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> a c F' e c G' | b F" e c G' | d G'
F' -> a c F' e F" | b F" e F" | d G' b
F" -> c G' b | (eps)

FIRST & FOLLOW sets

FIRST(G)  = { a, b, (eps) }               FOLLOW(G)  = { $ }
FIRST(G') = { b, (eps) }                  FOLLOW(G') = { $, b }
FIRST(G") = { a, b, d }                   FOLLOW(G") = { $ }
FIRST(F') = { a, b, d }                   FOLLOW(F') = { e }
FIRST(F") = { c, (eps) }                  FOLLOW(F") = { e }
Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Top-Down_Parsing/Exercise_3&oldid=6171"