Search code examples
parsingsyntaxbnf

Parsing left recursive grammar

I want to make a parser for a language that has left recursion and I don't know what to do. The only experience I have with parsing is with ll(1).

For example having the following bnf definition

cqlQuery    ::=     prefixAssignment cqlQuery
| scopedClause
prefixAssignment    ::=     '>' prefix '=' uri
| '>' uri
scopedClause    ::=     scopedClause booleanGroup searchClause
| searchClause
booleanGroup    ::=     boolean [modifierList]
boolean     ::=     'and' | 'or' | 'not' | 'prox'
searchClause    ::=     '(' cqlQuery ')'
| index relation searchTerm
| searchTerm
relation    ::=     comparitor [modifierList]
comparitor  ::=     comparitorSymbol | namedComparitor
comparitorSymbol    ::=     '=' | '>' | '<' | '>=' | '<=' | '<>' | '=='
namedComparitor     ::=     identifier
modifierList    ::=     modifierList modifier | modifier
modifier    ::=     '/' modifierName [comparitorSymbol modifierValue]
prefix, uri, modifierName, modifierValue, searchTerm, index     ::=     term
term    ::=     identifier | 'and' | 'or' | 'not' | 'prox' | 'sortby'
identifier  ::=     charString1 | charString2

Do I have to convert the left recursion or do something else to avoid it?

Please don't give me links for translators cause I want to do it manually and not use a program to do the parsing.

Solution

  • If you take a look at modifierList it is essentially requiring at least one modifier. We don't have to do much to get rid of the left recursion.

    modifierList ::= modifier [ modifierList ]

    Now scopedClause is a bit trickier but if we break out a second production it works out. It will always need at least one searchClause and can have many booleanGroup searchClause. 

    scopedClauseTail ::= booleanGroup searchClause [ scopedClauseTail ] 
scopedClause ::= searchClause [ scopedClauseTail ]