Re: Grammar -> Parser question (Dwight VandenBerghe)
9 Jun 1998 12:01:10 -0400

          From comp.compilers

Related articles
Grammar -> Parser question (1998-06-04)
Re: Grammar -> Parser question (Torbjorn Drevin) (1998-06-09)
Re: Grammar -> Parser question (Torben Mogensen) (1998-06-09)
Re: Grammar -> Parser question (1998-06-09)
Re: Grammar -> Parser question (Quinn Tyler Jackson) (1998-06-09)
Re: Grammar -> Parser question (Quinn Tyler Jackson) (1998-06-18)
| List of all articles for this month |

From: (Dwight VandenBerghe)
Newsgroups: comp.compilers
Date: 9 Jun 1998 12:01:10 -0400
Organization: All USENET --
References: 98-06-018
Keywords: parse

On 4 Jun 1998 23:40:01 -0400, wrote:

>How does one typically deal with this situation if one has to hand-code
>the parser? It looks like I need some sort of lookahead and/or backtracking
>mechanism so I can figure out which case I am dealing with.

Chris, you have stumbled into the "boolean/arithemtic expression"
quandry. It's an ongoing problem with most languages, and having
tried every approach I (or my advisers) have been able to devise over
the years, I recommend that you abandon the approach of trying to use
the parser to disambiguate the cases, and instead, parse all
expressions with one set of non-terminals, and disambiguate the two
cases (conditions and arithmetic expressions) in the type checker.
Your life will be easier, it will all work fine out of the box with
any decent parser generator, and it will be solid as a rock with no
hidden gotchas. I know, I know ... it's not all as it should be, this
is a chunk of lead in the midst of the platinum beauty of parsing
theory ... but sitting on the far end of 32 years in the field, 25 of
it writing compilers, I counsel you this way nonetheless:

    expr ::= factor [ '+' | '-' ] factor

    factor ::= ...

    primary ::= ID | INT | '(' expr ')'

... and let everything through into the initial AST as a valid
node, whether boolean or arithmetic. Then, in the logic that
handles the typing of "condition", make sure that the top-level
node can be coerced to boolean; if it can't, then signal a typing

Because, if you think about it ... that's what it really is.

[I agree, that's how I'd handle it too. You also get better error
messages since you can say "arithmetic expression found where boolean
required" rather than "syntax error at '+'" -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.