From this wikipedia page:
The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered. If the first alternative succeeds, the second alternative is ignored. Thus ordered choice is not commutative, unlike unordered choice as in context-free grammars and regular expressions. Ordered choice is analogous to soft cut operators available in some logic programming languages.
Why does PEG's choice operator short circuits the matching? Is it because to minimize memory usage (due to memoization)?
I'm not sure what the choice operator is in regular expressions but let's suppose it is this: /[aeiou]/
to match a vowel. So this regex is commutative because I could have written it in any of the 5! (five factorial) permutations of the vowel characters? i.e. /[aeiou]/
behaves the same as /[eiaou]/
. What is the advantage of it being commutative? (c.f. PEG's non-commutativity)
The consequence is that if a CFG is transliterated directly to a PEG, any ambiguity in the former is resolved by deterministically picking one parse tree from the possible parses. By carefully choosing the order in which the grammar alternatives are specified, a programmer has a great deal of control over which parse tree is selected.
Is this saying that PEG's grammar is superior to CFG's?
Parsing Expression Grammars (PEGs) [1] are an alternative formalism for describing a language's syntax. Unlike CFGs, PEGs are unambiguous by construction, and their standard semantics is based on recognizing strings instead of generating them.
PEG parsers are usually constructed as a recursive descent parser in which every rule in the grammar corresponds to a function in the program implementing the parser and the parsing expression (the “expansion” or “definition” of the rule) represents the “code” in said function.
Parsing is the process of analysing a string of symbols, expressed in natural or computer languages that will accord formal grammar. Expression Parsing in Data Structure means the evaluation of arithmetic and logical expressions.
A formal grammar is "context-free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.
Traditionally, parsing is done by taking a sentence and breaking it down into different parts of speech. The words are placed into distinct grammatical categories, and then the grammatical relationships between the words are identified, allowing the reader to interpret the sentence.
A CFG grammar is non-deterministic, meaning that some input could result in two or more possible parse-trees. Though most CFG-based parser-generators have restrictions on the determinability of the grammar. It will give a warning or error if it has two or more choices.
A PEG grammar is deterministic, meaning that any input can only be parsed one way.
To take a classic example; The grammar
if_statement := "if" "(" expr ")" statement "else" statement | "if" "(" expr ")" statement;
applied to the input
if (x1) if (x2) y1 else y2
could either be parsed as
if_statement(x1, if_statement(x2, y1, y2))
or
if_statement(x1, if_statement(x2, y1), y2)
A CFG-parser would generate a Shift/Reduce-conflict, since it can't decide if it should shift (read another token), or reduce (complete the node), when reaching the "else" keyword. Of course, there are ways to get around this problem.
A PEG-parser would always pick the first choice.
Which one is better is for you to decide. My opinion is that often PEG-grammars is easier to write, and CFG grammars easier to analyze.
I think you're confusing CFG with LR and with ambiguity. Grammars are not deterministic/nondeterministic, though their parsers may be. An ambiguous grammar is still CFG if it complies with the definition, and a deterministic parser can be built for it doing what PEG does.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With