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 … Read more
At a high level, the difference between LR(0), LALR(1), and LR(1) is the following: An LALR(1) parser is an “upgraded” version of an LR(0) parser that keeps track of more precise information to disambiguate the grammar. An LR(1) parser is a significantly more powerful parser that keeps track of even more precise information than an … Read more
An important detail here is that grammars do not accept strings; they generate strings. Grammars are descriptions of languages that provide a means for generating all possible strings contained in the language. In order to tell if a particular string is contained in the language, you would use a recognizer, some sort of automaton that … Read more
It’s not always easy (or even possible) to demonstrate that a grammar is ambiguous, but if there is a short ambiguous sentence, then it can be found with brute-force enumeration, which is what I believe that tool does. And the output is revealing; the shortest ambiguous sentence is the empty string. So it remains only … Read more
Being context free is first a property of generative grammars. It means that what a non-terminal can generate will not depend on the context in which the non-terminal appears (in non context-free generative grammar, the very notion of “string generated by a given non-terminal” is in general difficult to define). This doesn’t prevent the same … Read more
Pattern Recursion With recursive patterns, you have a form of recursive descent matching. This is fine for a variety of problems, but once you want to actually do recursive descent parsing, you need to insert capture groups here and there, and it is awkward to recover the full parse structure in this way. Damian Conway’s … Read more
What programming languages are context-free? […] My gut tells me that functional languages might be context-free […] The short version: There are hardly any real-world programming languages that are context-free in any meaning of the word. Whether a language is context-free or not has nothing to do with it being functional. It is simply a … Read more
LL is usually a more efficient parsing technique than recursive-descent. In fact, a naive recursive-descent parser will actually be O(k^n) (where n is the input size) in the worst case. Some techniques such as memoization (which yields a Packrat parser) can improve this as well as extend the class of grammars accepted by the parser, … Read more
Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar. So for a palindrome for instance, is of the form, S->ABA A->something B->something You can clearly see that palindromes cannot be expressed … Read more
A context free grammar is a grammar which satisfies certain properties. In computer science, grammars describe languages; specifically, they describe formal languages. A formal language is just a set (mathematical term for a collection of objects) of strings (sequences of symbols… very similar to the programming usage of the word “string”). A simple example of … Read more