5 ms·

HN formatting messed up your asterisks. The whole rule is: multiplicative : primary "" multiplicative { return $1 $3; } / prim

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?
      - cynicalkane 17y ago
        The approach I'm working on uses the same "growing the seed" idea, but in a different way. It involves the memo entries being able to remember which left-recursive results they are dependent on. This way, when a left-recursive rule produces a result that is dependent on itself, it knows that this match can possibly be "grown" through repeated iterations. That's a basic sketch of the idea. Performance properties remain the same in the case of left-recursive rules that are not interdependent. I don't really know what they are like for large numbers of interdependent left-recursive rules--but if you have a language like that, better to use an Earley or GLR parser. I'm still working on it. It passes a battery of test cases, two of which I posted above, but I'm not 100% confident in it just yet. Also, as posted above, I'm trying to get permission from the higher-ups to release the code into the wild.

HN formatting messed up your asterisks. The whole rule is: multiplicative : primary "*" multiplicative { return $1 * $3; } / prim

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?
    - cynicalkane 17y ago
      The approach I'm working on uses the same "growing the seed" idea, but in a different way. It involves the memo entries being able to remember which left-recursive results they are dependent on. This way, when a left-recursive rule produces a result that is dependent on itself, it knows that this match can possibly be "grown" through repeated iterations. That's a basic sketch of the idea. Performance properties remain the same in the case of left-recursive rules that are not interdependent. I don't really know what they are like for large numbers of interdependent left-recursive rules--but if you have a language like that, better to use an Earley or GLR parser. I'm still working on it. It passes a battery of test cases, two of which I posted above, but I'm not 100% confident in it just yet. Also, as posted above, I'm trying to get permission from the higher-ups to release the code into the wild.