Difference between revisions of "Bottom-Up Parsing/Example 5: LALR(1)"

From Wiki**3

< Bottom-Up Parsing
(Created page with "{{TOCright}} = Problem = Consider the following grammar. C is the start symbold and { w, x, y, z } is the set of terminal symbols. A → y | ε B → C x | x A C → D x B |...")
 
(→‎Problem)
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{TOCright}}
 
{{TOCright}}
−
= Problem =
+
== Problem ==
  
−
Consider the following grammar. C is the start symbold and { w, x, y, z } is the set of terminal symbols.
+
Consider the following grammar. '''C''' is the start symbold and '''{ w, x, y, z }''' is the set of terminal symbols.
  
 
  A → y | ε
 
  A → y | ε
Line 12: Line 12:
 
# Tal como apresentada, a gramática pode ser processada por um analisador LL(1)? Justifique.
 
# Tal como apresentada, a gramática pode ser processada por um analisador LL(1)? Justifique.
 
# Compacte a tabela de análise (de 1.), eliminando reduções unitárias e quase unitárias, bem como propagando reduções que permitam compactar a tabela.
 
# Compacte a tabela de análise (de 1.), eliminando reduções unitárias e quase unitárias, bem como propagando reduções que permitam compactar a tabela.
−
# Apresente a tabela com o conteúdo da pilha do analisador, a entrada e a acção realizada em cada passo da análise, para a sequência de entrada z x x y. Em caso de conflitos, assuma o comportamento da ferramenta YACC.
+
# Apresente a tabela com o conteúdo da pilha do analisador, a entrada e a acção realizada em cada passo da análise, para a sequência de entrada '''z x x y'''. Em caso de conflitos, assuma o comportamento da ferramenta YACC.
  
 
== Solution ==
 
== Solution ==
  
−
[[category:Teaching]]
+
Small bug: state 9 has {$,x} as lookahead set (and not only {x}).
−
[[category:Compilers]]
+
 
 +
* [[Media:co12-2012060603.pdf|solution (draft)]]
 +
 
 +
[[category:Compiladores]]
 +
[[category:Ensino]]

Latest revision as of 11:52, 2 May 2024

Problem

Consider the following grammar. C is the start symbold and { w, x, y, z } is the set of terminal symbols. 

A → y | ε
B → C x | x A
C → D x B | A w
D → w | z | ε
  1. Construa a tabela de análise para um analisador sintáctico ascendente LALR(1) para esta gramática, indicando o conjunto de estados do analisador e os símbolos de antevisão. A gramática é SLR(1)? Justifique.
  2. Tal como apresentada, a gramática pode ser processada por um analisador LL(1)? Justifique.
  3. Compacte a tabela de análise (de 1.), eliminando reduções unitárias e quase unitárias, bem como propagando reduções que permitam compactar a tabela.
  4. Apresente a tabela com o conteúdo da pilha do analisador, a entrada e a acção realizada em cada passo da análise, para a sequência de entrada z x x y. Em caso de conflitos, assuma o comportamento da ferramenta YACC.

Solution

Small bug: state 9 has {$,x} as lookahead set (and not only {x}).

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Bottom-Up_Parsing/Example_5:_LALR(1)&oldid=16340"