4 ms·

I'm confused about the grammar example. How does: multiplicative : primary "* " multiplicative { return $1 * $3; } return the product of two integers?

mbrubeck 17y ago
HN formatting messed up your asterisks. The whole rule is: multiplicative : primary "*" multiplicative { return $1 * $3; } / primary "primary" refers to another rule in the grammar, which is defined as integer or a parenthesized expression. This snippet defines "multiplicative", which is either a primary, or a primary followed by an asterisk followed by another multiplicative. (This recursively expands to allow any number of primaries, separated by asterisks.) The value of the multiplicative expression is the value of the first term times the value of the third term. (The second term is just the literal string "*".)
- euroclydon 17y ago
  Thanks, what I don't get from reading the grammar is how, as you say, multiplicative is either a primary or primary followed by a multiplicative. Clearly I understand that it needs to be defined this way, but is that either part just inherit to PEG or this implementation or what, b/c I don't get it form the syntax?
  - mbrubeck 17y ago
    The "/" at the start of the second line is a choice operator. For example, this is how you would define a term a that can match either b or c: a: b / c (The asterisks in my post were escaped because they were in a code block, or because there were not two of them in the same line.)
- euroclydon 17y ago
  btw, how did you escape that asterisk in quotes?
- barrkel 17y ago
  On the face of it, however, the grammar is problematic. There's a reason it uses "additive", "multiplicative" and "primary" rather than a more traditional expression, term and factor: by using commutative operators like + and multiply, and leaving out - and / it disguises the fact that the grammar is actually evaluating the expression from right to left, rather than the expected order of left to right.
  - dmajda 17y ago
    I knew somebody would raise this point :-) You are right that the evaluation order would be wrong for "-" and "/". I will probably implement support for left recursion in PEG.js - it is possible (see e.g. http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf). After that, the grammar could be rewritten to evaluate in the correct order. (Another alternative - which works right now - is to change the parsing expressions to something like "additive ([+-] additive)*" and deal with the whole chain of operations with the same priority at once. I didn't use this in the example as I wanted it to be as simple as possible.)
    - cynicalkane 17y ago
      Don't use that paper! I tried to use the parsing technique in that paper while working on a parser for use at the CME, and it caused me weeks of headaches. First, you'll note the algorithm is extremely complicated--nothing like the simple top-down algorithm that makes PEGs so attractive. Not only is it complicated, it misses basic refactoring issues--some logic is duplicated across functions, and the functions interact in ugly ways. Second, it doesn't even handle left recursion correctly. Throw a ruleset like this at their parser A -> B "a" B -> C "b" C -> B / A / "c" and it will explode into a million little pieces, because the authors did not account for any recursive rule having multiple recursion points. Don't even try something like S -> A / B A -> A "a" / B / a B -> B "b" / A / "b"
      - dmajda 17y ago
        Interesting, thanks for the warning. I only skimmed through the paper today and noted that the algoritm seems complex, but I didn't attempt to understand it in detail. What was your final result? Did you implement the left recursion in the way the paper describes, invented/found some other way or abandoned the whole idea?
deleted 17y ago
[deleted]

mbrubeck 17y ago

HN formatting messed up your asterisks. The whole rule is: multiplicative : primary "*" multiplicative { return $1 * $3; } / primary "primary" refers to another rule in the grammar, which is defined as integer or a parenthesized expression. This snippet defines "multiplicative", which is either a primary, or a primary followed by an asterisk followed by another multiplicative. (This recursively expands to allow any number of primaries, separated by asterisks.) The value of the multiplicative expression is the value of the first term times the value of the third term. (The second term is just the literal string "*".)

euroclydon 17y ago
Thanks, what I don't get from reading the grammar is how, as you say, multiplicative is either a primary or primary followed by a multiplicative. Clearly I understand that it needs to be defined this way, but is that either part just inherit to PEG or this implementation or what, b/c I don't get it form the syntax?
- mbrubeck 17y ago
  The "/" at the start of the second line is a choice operator. For example, this is how you would define a term a that can match either b or c: a: b / c (The asterisks in my post were escaped because they were in a code block, or because there were not two of them in the same line.)
euroclydon 17y ago
btw, how did you escape that asterisk in quotes?
barrkel 17y ago
On the face of it, however, the grammar is problematic. There's a reason it uses "additive", "multiplicative" and "primary" rather than a more traditional expression, term and factor: by using commutative operators like + and multiply, and leaving out - and / it disguises the fact that the grammar is actually evaluating the expression from right to left, rather than the expected order of left to right.
- dmajda 17y ago
  I knew somebody would raise this point :-) You are right that the evaluation order would be wrong for "-" and "/". I will probably implement support for left recursion in PEG.js - it is possible (see e.g. http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf). After that, the grammar could be rewritten to evaluate in the correct order. (Another alternative - which works right now - is to change the parsing expressions to something like "additive ([+-] additive)*" and deal with the whole chain of operations with the same priority at once. I didn't use this in the example as I wanted it to be as simple as possible.)
  - cynicalkane 17y ago
    Don't use that paper! I tried to use the parsing technique in that paper while working on a parser for use at the CME, and it caused me weeks of headaches. First, you'll note the algorithm is extremely complicated--nothing like the simple top-down algorithm that makes PEGs so attractive. Not only is it complicated, it misses basic refactoring issues--some logic is duplicated across functions, and the functions interact in ugly ways. Second, it doesn't even handle left recursion correctly. Throw a ruleset like this at their parser A -> B "a" B -> C "b" C -> B / A / "c" and it will explode into a million little pieces, because the authors did not account for any recursive rule having multiple recursion points. Don't even try something like S -> A / B A -> A "a" / B / a B -> B "b" / A / "b"
    - dmajda 17y ago
      Interesting, thanks for the warning. I only skimmed through the paper today and noted that the algoritm seems complex, but I didn't attempt to understand it in detail. What was your final result? Did you implement the left recursion in the way the paper describes, invented/found some other way or abandoned the whole idea?

deleted 17y ago

[deleted]