Geek Answers Handbook

Grammar: the difference between top to bottom and bottom to top? (Example)

This is the next question from the Grammar: the difference between top to bottom and bottom to top?

I understand from this question that:

  • the grammar itself is not from top to bottom or from bottom to top, the parser
  • there are grammars that can be analyzed by one and not by the other
  • (thanks Jerry Coffin

So, for this grammar (all possible mathematical formulas):

E -> ETE E -> (E) E -> D T -> + | - | * | / D -> 0 D -> LG G -> GGG -> 0 | L L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Will it be readable by the parser from top to bottom and from bottom to top?

Could you say that this is a top-down grammar or a lower grammar (or not)?

I ask because I have a homework question that asks:

"Write grammar from top to bottom and bottom to top for a language consisting of all ..." (different questions)

I am not sure if this can be right, because it seems that there is no such thing as grammar from top to bottom and from bottom to top. Can anyone clarify?

+7
grammar topdown
source share
1 answer

This grammar is stupid because it combines lexing and parsing as one. But well, this is an academic example.

The thing with shrubs and from top to bottom is that it has special corner cabinets that are difficult to implement with you. I probably think you should check to see if he has any problems and change the grammar.

To understand the grammar, I wrote the correct EBNF

 expr: expr op expr | '(' expr ')' | number; op: '+' | '-' | '*' | '/'; number: '0' | digit digits; digits: '0' | digit | digits digits; digit: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

I especially don't like the digits: digits digits rule digits: digits digits . It is not clear where the first digits begin, and the second ends. I would follow the rule as

 digits: '0' | digit | digits digit;

Another problem: number: '0' | digit digits; number: '0' | digit digits; This conflicts with digits: '0' and digits: digit; . This is actually duplicated. I would change the rules to (delete numbers):

 number: '0' | digit | digit zero_digits; zero_digits: zero_digit | zero_digits zero_digit; zero_digit: '0' | digit;

This makes the LR1 grammar (left recursive with one look ahead) and context free. This is what you usually give to a parser generator, such as a bison. And since the bison is at the bottom, this is a valid input for the residue analyzer.

For a top-down approach, at least for a recursive decent, a left recursive is a problem. You can use rollback if you want, but for this you need the grammar RR1 (on the right is recursive). To do this, replace the recursion:

 zero_digits: zero_digit | zero_digit zero_digits;

I am not sure if this answers your question. I think this question is poorly worded and misleading; and I am writing a parser for life ...

+5
source share

More articles:


All Articles