CODEWITHSUNDEEP
c++linuxbison
Amumu
Amumu

Reputation: 18572

Implement a loop in Bison using BNF

So, I got this code:

calclist: /* nothing */   matches at beginning of input
 | calclist exp EOL { printf("= %d\n", $1); } EOL is end of an expression
 ;

It is explained that:

the first two rules, which define the symbol calcset, implement a loop that reads an expression terminated by a newline and prints its value. The definition of calclist uses a common two-rule recursive idiom to implement a sequence or list: the first rule is empty and matches nothing; the second adds an item to the list. The action in the second rule prints the value of the exp in $2.

From the book "Flex and Bison". Can someone please tell me how such syntax imply a loop? I can understand the recursion in the exp (which is written later, but I don't include because it's irrelevant here). However, look at such syntax, I can only think of the first rule matches nothing to keep the parser processes nothing, thus having infinite loop until the first symbol is given from standard input stream and start the second rule. However, I don't understand the second rule. How can it ever reach the exp part? Wouldn't it keep recurse when it encounters calclist?

Upvotes: 1

Views: 710

Answers (2)

thekoalaz
thekoalaz

Reputation: 76

The second rule implies a loop as if you had a line such as:

exp EOL exp EOL exp EOL exp EOL

Each of those "exp EOL"s is a calclist, that's included inside another calclist. Therefore the rules would reduce that line as such:

exp EOL exp EOL exp EOL exp EOL
calclist1 exp EOL exp EOL exp EOL exp EOL < - Rule 1. calclist1 is [ ], the empty string.
calclist2 exp EOL exp EOL exp EOL < - Rule 2. calclist2 is calclist1 exp EOL
calclist3 exp EOL exp EOL < - Rule 2. calclist3 is calclist2 exp EOL
calclist4 exp EOL < - Rule 2. calclist4 is calclist3 exp EOL
calclist5 < - Rule 2. calclist5 is calclist4 exp EOL

This is what it means by it creating a loop. Like the part you quoted, this is a common "idiom" when defining grammars in order to create a list of expressions of arbitrary length.

I hope that answers your question.

Thanks!

Upvotes: 4

500 - Internal Server Error
500 - Internal Server Error

Reputation: 28839

If would if this were a recursive descent parser, but I guess the point is that it is not.

Upvotes: 1

Related Questions