Converting EBNF to BNF for an LALR parser

4
votes

I know there are several posts with a similar title. Most link to a dead site - and I have a more specific question anyways.

I'm trying to convert the EBNF in the XPath spec to straight BNF so that I can easily create a Bison-compatiable grammar file.

It's been a while since I've done this, and I don't remember which side of the production a recursion belongs. I thought it was the left - but my "straight-forward" translation is giving me syntax errors with plain-jane XPath expressions when they are run through the Bison-generated parser.

So if someone could humor me and weigh in - so I'm not chasing a ghost:

In the Expr rule below:

Expr::=     
    ExprSingle ("," ExprSingle)*

Is this the correct translation? (putting the recursion on the left):

Expr::= 
    Expr "," ExprSingle
    | ExprSingle
2
parsinggrammarbisonbnfebnf
That's fine.... You could put the recursion on the right and it should work, but you'll make the parser "do more work" as it has to track the spine of the recursion, and to do so it has to use more stack locations. – Ira Baxter
@IraBaxter Could you post that comment as an answer for me? – Steve

2 Answers

4
votes

That's fine....

You could put the recursion on the right and it should work, but you'll make the parser "do more work" as it has to track the spine of the recursion, and to do so it has to use more stack locations.

0
votes

Your translation is left recursive on the rule Expr and it accepts other Expr productions.

The correct translation would be:

Expr::=
    ExprSingle Expr1
Expr1::=
    Expr1 "," ExprSingle | ε