CODEWITHSUNDEEP
parsinggrammarcontext-free-grammar
Lily Mara
Lily Mara

Reputation: 4138

Is this grammar ambiguous, or is it the library's fault?

I'm using the rust-peg parsing expression grammar library, but the principles should be generally understandable. I'm using the library to create a parser for go based on the spec. I'm having trouble getting if statements to parse, and I've distilled the issue down to a simple example.

sep
    = ( " " / "\n" )*

expression
    = "x" sep block
    / "x"

if_stmt
    = "if" sep expression sep block

block
    = "{" ( sep stmt )* "}"

stmt
    = if_stmt
    / expression

pub file
    = ( sep stmt )*

This grammar should (in my mind) parse a very simple language that contains two types of statements: If statements and expression statements. An expression can be x, or x followed by a block. An if statement is if followed by an expression, followed by a block. Here is an example input that my grammar fails to parse:

x {}
if x {

}

This fails to parse because the curly braces after the x in the if statement line are interpreted as a block as a part of the "x" sep block rule, and not a block as a part of the if_stmt rule. Unfortunately, this parsing library does not backtrack and try re-parsing this part of the line as the if statement's block when this fails. I have realized that if I switch the order of the expression rule so that it tries to parse "x" first, then the if statement parses just fine. This does create a problem for the line x {}, since the x at the beginning of the line parses as just a normal "x", and it backs out of the expression rule before it tries to parse the {}.

Do these limitations make the library incapable of parsing a grammar like this? Should I find another one, or just write my own parser? (I don't really want to do that)

Edit

I experimented with the go grammar, and I discovered that it is not legal to put a struct literal (the "x" sep block example) in an if statement condition. I was thus able to disambiguate the grammar as attdona suggested.

Upvotes: 0

Views: 84

Answers (1)

attdona
attdona

Reputation: 18993

Try to disambiguate your grammar:

simple_expr
    = "x"

block_expr
    = "x" sep block

expression
    = simple_expr
    / block_expr

if_stmt
    = "if" sep simple_expr sep block

I don't know rust-peg, I hope this may help to resolve the parsing of your grammar.

Upvotes: 1

Related Questions