Talk:Parsing expression grammar

From Wikipedia, the free encyclopedia

I'm not convinced that the grammar listed for {aⁿbⁿcⁿ:n > 0} is correct.

A ← (a A b)?

B ← (b B c)?

A matches any number of a's followed by the same number of b's. B matches any number of b's followed by the same number of c's.

S ← &(A !b) a* B !c

&(A !b) ensures that we have any number of a's followed by the exactly the same number of b's. a* consumes all the a's, and then B !c matches any number of b's followed by the exactly the same number of c's.

In other words, A and B overlap: they match the same string of b's. They are more symmetrical that the rule suggests.

The problem is that the A and B rules also match the empty string, so this grammar accepts for n=0, which per the prose, it shouldn't. (Also, since we know there should be at least one a, we can use a+ instead of a*).

I'm going to change the A and B rules not to match the null string, the S rule to use a+, and use math markup for the equation (and n >= 1 rather than n > 0, both for consistency with Context-sensitive grammar).

Malcolm rowe 13:06, 26 September 2005 (UTC)

(Removing my own earlier comment.) QTJ 05:23, 11 October 2006 (UTC)

---

What does REBOL have to do with parsing expression grammars? Using them or providing a mechanism to use them doesn't count.

[edit] Please clarify N and Σ in the examples

The definition of a parsing expression grammar says it consists of

a finite set N of nonterminal symbols
a finite set Σ of terminal symbols that is disjoint from N
a finite set P of parsing rules

Please provide clearly and explicitly in all of the examples, what all three of these are.

S <- if C then S else S / if C then S

"if" "then" and "else" are in the finite set of terminal symbols? If so, then say so. And so forth for the rest of the examples.

thank you. --LAM 66.28.244.66 17:04, 15 May 2006 (UTC)

[edit] First example is incorrect.

The first example (PEG for mathematical formulas that use the basic four operations) is incorrect. It allows expressions such as 3.2 + ..2..3..000

Only a single period should be allowed. —The preceding unsigned comment was added by HappyDog (talk • contribs).

Thanks, that's a good point. I think the best way is just to take out the decimal point, and only allow the example to recognize non-negative integers. If it's supposed to cover real numbers, it needs a negative sign too, and some needlessly complex parsing rules. I've changed the example to just use non-negative integers. rspeer / ɹəədsɹ 23:37, 25 May 2006 (UTC)

A good solution. Thanks for the prompt reply. --HappyDog 17:07, 26 May 2006 (UTC)

[edit] Suggest Merge of Packrat Parser Into This

I suggest that the packrat parser article stub be merged into this article. Since I am a parsing technology author myself, I recuse myself from the discussion beyond this suggestion, to avoid conflicts-of-interest. My rational is that packrat parsing is not widely enough adopted to get a full stub. Packrat parser could then be a redirect to this page, instead.

-- QTJ 00:40, 19 October 2006 (UTC)