Convert grammar into an LL(1) grammar which recognises the same language

ambiguitycompilergrammar

I have the following sample question for a compilers exam and wanted to check my solution.

Convert the following grammar into an LL(1) grammar which recognises the same 
language:

E -> E + T  
E -> T  
T -> id 
T -> id() 
T -> id(L) 
L -> E;L 
L -> E

For my answer I have

E  -> T E'  
E' -> + T | ε  
T  -> id 
T  -> id() 
T  -> id(L) 
L  -> E L' 
L' -> ;E | ε

Can anybody verify the answer?

Edit

Ok so would it be similar to…

E  -> T E'  
E' -> + E | ε  
T  -> id 
T  -> id() 
T  -> id(L) 
L  -> E L' 
L' -> ;E | ε

Best Answer

E -> E + T | T
T -> id | id() | id(L)
L -> E;L | E

E -> TE'
E'-> +TE' | ε

L -> E;L | E

L -> EL'
L'-> ;L | ε

you need to transform T as I did with L otherwise it will be an LL(3)

Related Solutions

Java Parsing – Better Design Alternatives for Special Cases

Predictive parser you selected (LL(k)) means you will have to solve left-recursion problems. Algorithm for solving direct and indirect recursions is clearly described on wikipedia:

http://en.wikipedia.org/wiki/Left_recursion

Some info can be found in posts here on StackOverflow:

https://stackoverflow.com/questions/2652060/removing-left-recursion https://stackoverflow.com/questions/2999755/removing-left-recursion-in-antlr https://stackoverflow.com/questions/4994036/left-recursion-elimination

In human language (non-scientific :) "left-recursion problem" means you can't endlessly go into recursion with non-terminal (A -> Ab) again and again. At some time you HAVE TO feed parser algorithm with a terminal to breake a loop.

In BNF this could look like:

Recursion Problem:

NT: NT T
NT: T

One solution:

NT: T NT2
NT2: T NT2
NT2:

For your grammar this could look like:

DataType:
    PrimitiveDataType ArrayDimensions
 |  ComplexDataType ArrayDimensions

ArrayDimensions:
    [] ArrayDimensions
 |

If your parser generator doesn't allow empty productions and/or if you want to process array types separately, try something like this:

DataType:
    DataTypeName
 |  ArrayDataType

ArrayDataType:
    DataTypeName ArrayDimensions

DataTypeName:
    PrimitiveDataType
 |  ComplexDataType

ArrayDimensions:
    []
 |  [] ArrayDimensions

Finite State Automaton – Constructing for a Given Regex

No, your deterministic finite automaton is incorrect. Your regular expression is.

The problem in your DFA is the declaration of 5 and 6 to be terminal nodes. A testcase such as "0." will be accepted by your DFA even though it should not.

Optional values

I want to point out how you can model a general structure which includes optional values. Let's take for example a regular expression like "a?b". The idea now is to create two branches. One includes the optional element "a" and the other one excludes it. The inclusion branch merges with the other one with the first value that is obligatory again.

Modelling optional values

One time or more

As a second idea: How do we model quantities such as "once or more times"? We have to create an edge which requires us to read the symbol "a" one time. After that we create a self-loop which reads the symbol as many times as necessary (possibly zero).

Modelling one or more times in a DFA

Applying those ideas to your Deterministic Finite Automaton, we get the following:

Deterministic Finite Automaton

Non-deterministic Finite Automatons

An automaton becomes non-deterministic if there are two edges with the same label starting at the same vertex. In the example below starting with vertex "4" and reading the input "0", you won't know which path will accept the input string (left or down) and will proceed non-deterministically.

Non-deterministic Finite Automaton