About Parsing Potentially Ambiguous Context-Free Grammars
Given a context-free grammar , how to check if ?
- recursive descent gives efficient answer when is LL(1)
- we now see how to do it for arbitrary context-free grammar
- applications in Natural Language Processing
- parsing mathematical formulas: e.g. the parser within the Isabelle interactive theorem prover
- more flexibility in writing the grammar for programming languages
Example from Natural Language Processing:
A student gets a good recommendation letter if the student makes a good impression on Viktor or makes a good impression on Giuliano and does an excellent project.
Interpretation on the condition for good recommendation letter:
In program natural language processing we need to represent multiple possible interpretations and resolve them using other methods (probabilities derived from a training set, or semantic interpretation using automated reasoning tools in some semantic domain).
Example from parsing formulas:: The Isabelle interactive theorem prover supports higher-order logic, which contains typed lambda calculus and first-order logic. The theorem prover has a flexible syntax that allows writing expressions close to the common mathematical practice. for example
makes denote the function such that and for . Unfortunatelly, the above expression looks like application of function to some value of the form , so it can be difficult to parse. Another example in Isabelle are expressions denoting sets. The formula
denotes a singleton set containing two elements: the first element is a triple , the second element is . On the other hand, the expression
is a set comprehension denoting infinitely many elements. These two expressions can also be difficult to differentiate in simple parsers.