I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new non-terminal characters for the same.

For example,

<assignmentstats>------- <type><id>=<E>/ id=<E>/id'['<E>']'=<E>/     

is transformed to

<assignmentstats>------- <type><id>=<E>/ id<LF3>
<LF3>------- =<E>/[<E>]=<E>

After applying such rules for all the required statements, I expected an unambiguous grammar.

But the following statement is somehow still ambiguous.

<body>------- <forrelatedstuff>/ <floors>/<stats> 

Here are the related statements of the grammar(only those required has been shown)

<funcbody>----- {<stats>}    
<stats>----- <stat> <stats>/ #       
<floors>-------- <floor><floors>/ #     
<floor>------- floo <id><arr>{stats}/id<arr>{<stats>}     
<stat>----- <superstats>/<returnstats>
<superstats>----- <type>id<Zip>/id<LF3>  
<building> ------- build <id> {<body>}   
<returnstats>--------- return <E>  

I looked more into it , and found that the ambiguity is between 'floors' and 'stats'. The first('stats') and first('floors), i.e. the set of first terminal characters contain 'id' and '}' for both.

I can see why this would be a problem and how left factoring could solve this. How can I remove such kind of ambiguity through left factoring?

Note: Here, 'id' denotes an identifier.

'#' denotes epsilon.

  • 2
    $\begingroup$ Left-factoring removes left-recursion; why do you think it can do away with ambiguity? $\endgroup$ – Raphael Feb 7 '15 at 11:52
  • $\begingroup$ Without left factoring, the parser may need to lookahead more than one element(terminal symbol) to decide which route(grammar transition rule) to take. Left factoring removes this ambiguity, making the grammar LL(1). $\endgroup$ – spiderbat Feb 7 '15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.