Question

This is for a Theoretical Foundations of Computer Science course:

1)Show that every LL(1)-language is indeed a q-language.

2)Discuss the differences between pushdown automata and top-down parsers. Can parsers be made into pushdown automata?

Answer 1

1)

Any grammar that is LL(1) defines an LL(1) language. By definition, a language is LL(1) if there is some grammar that generates it that is LL(1), so the fact that you have an LL(1) grammar for the language automatically means that the language is LL(1).

To elaborate, a language is a set of strings and a grammar for that language is a means of describing that language. Some languages have LL(1) grammars while others do not. However, the fact that a grammar is not LL(1) does not mean that the language it describes is not. For example, consider this grammar:

A -> ab | ac

This grammar is not LL(1) because it contains a FIRST/FIRST conflict when trying to predict the production for A when seeing terminal a. However, it describes an LL(1) language, since the language is also described by the grammar

A -> aX
X -> b | c

So the language generated by these grammars (which just contains ab and ac) is indeed LL(1).

2) Pushdown Automata & Parsing. Parsing is used to derive a string using the production rules of a grammar. It is used to check the acceptability of a string. ... Top-Down Parser − Top-down parsing starts from the top with the start-symbol and derives a string using a parse tree.

A parser can be of two types −

• Top-Down Parser − Top-down parsing starts from the top with the start-symbol and derives a string using a parse tree.

• Bottom-Up Parser − Bottom-up parsing starts from the bottom with the string and comes to the start symbol using a parse tree.

Design of Top-Down Parser

For top-down parsing, a PDA has the following four types of transitions −

• Pop the non-terminal on the left hand side of the production at the top of the stack and push its right-hand side string.

• If the top symbol of the stack matches with the input symbol being read, pop it.

• Push the start symbol ‘S’ into the stack.

• If the input string is fully read and the stack is empty, go to the final state ‘F’.

Example

Design a top-down parser for the expression "x+y*z" for the grammar G with the following production rules −

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

Solution

If the PDA is (Q, ∑, S, δ, q₀, I, F), then the top-down parsing is −

(x+y*z, I) ⊢(x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢(x+y*z, X+XI)

⊢(x+y*z, Y+X I) ⊢(x+y*z, x+XI) ⊢(+y*z, +XI) ⊢ (y*z, XI)

⊢(y*z, X*YI) ⊢(y*z, y*YI) ⊢(*z,*YI) ⊢(z, YI) ⊢(z, zI) ⊢(ε, I)

Design of a Bottom-Up Parser

For bottom-up parsing, a PDA has the following four types of transitions −

• Push the current input symbol into the stack.

• Replace the right-hand side of a production at the top of the stack with its left-hand side.

• If the top of the stack element matches with the current input symbol, pop it.

• If the input string is fully read and only if the start symbol ‘S’ remains in the stack, pop it and go to the final state ‘F’.

Example

Design a top-down parser for the expression "x+y*z" for the grammar G with the following production rules −

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

Solution

If the PDA is (Q, ∑, S, δ, q₀, I, F), then the bottom-up parsing is −

(x+y*z, I) ⊢ (+y*z, xI) ⊢ (+y*z, YI) ⊢ (+y*z, XI) ⊢ (+y*z, SI)

⊢(y*z, +SI) ⊢ (*z, y+SI) ⊢ (*z, Y+SI) ⊢ (*z, X+SI) ⊢ (z, *X+SI)

⊢ (ε, z*X+SI) ⊢ (ε, Y*X+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)

Pushdown automata are used in theories about what can be computed by machines. ... Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design.