Grammar question (Elan Feingold)
Tue, 20 Sep 1994 21:31:43 GMT

          From comp.compilers

Related articles
Grammar question (1994-09-20)
Re: Grammar question (1994-09-22)
Re: Grammar question (Chris Clark USG) (1994-09-26)
Re: Grammar question (Zerksis D. Umrigar) (1994-09-28)
grammar question (1996-03-14)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Elan Feingold)
Keywords: parse, yacc, question, comment
Organization: Digital Equipment Corporation
Date: Tue, 20 Sep 1994 21:31:43 GMT

I am trying to use lex and yacc to parse the following sorts
of "sentences":

"Verb Foo Foo Foo Bar Bar FooBar Foo"

Where the stream of lexemes returned should be:


according to the following grammar:

Command -> Expression FOO Identifier BAR Identifier FOOBAR Identifier
Expression -> Identifier | Expression + Expression ... etc ...
Identifier -> IDENTIFER | NUMBER

This is similar to the FORTRAN problem where there are NO RESERVED
WORDS. What makes this harder is that each part of the sentence is
optional, as follows:

Command -> [Expression] [FOO Identifier] [BAR Identifier] [FOOBAR Identifier]

Where each of the parts in [] can be left out. The problem is that
when I type "Verb Foo..." I don't know whether this should be returned
as an IDENTIFIER or a FOO, without looking ahead to see if down the
line to see if there is another "Foo." If I type something like

"Verb Foo+2/Foo Foo Foo" I want the first two Foos and the last
Foo to be returned as IDENTIFIERs and the second Foo as a FOO.
I realize that if the Expression required a keyword in front of it,
such as "EXPR" the problem would be much simpler, and I could use
some sort of variable to keep track of what I had lexed, i.e.

typedef enum _LexerMemory { afterNothing, afterExpr, afterFoo, afterBar....}..

And return the keyword the first time around and IDENTIFIER after that.
However, I am a slave of the existing grammar :(

I would GREATLY appreciate any help!

Thanks in advance,

|| Elan Feingold (Cornell '94)
|| Software Engineer II
|| Digital Equipment Corporation
|| Work: 603.881.1115
[My experience suggests that the only way to do this in yacc is to put a
horrendous amount of lookahead glop into the lexer, frequently combined
with hints from the parser, so that the lexer can feed the parser tokens
it can handle. I managed to parse Fortran 77 in yacc that way. -John]

Post a followup to this message

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