This video above reveals the history of parsing, the mechanism behind context free grammar, and an overview of the various methods such as the Earley Parser. If we look at Github we can see that Ohad has made significant progress on the Earley Parser. The Earley Parser has a component algorithm called a Recognizer and from this Recognizer there is a desired state called shared packed parse forest. To reach this desired state we can see in the paper SPPF-Style Parsing From Earley Recognisers. Needless to say this process is extremely complicated and beyond my ability to explain it in detail but I do make note of it for people who would like to gain deeper knowledge of exactly what is going on in Github.
- In the video the concept of the grammar flow graph (GFG) is introduced.
- This GFG helps us to visualize parsing by turning them into path problems.
What is a parse forest? An input string is turned into a CFG and all derivations of a given input string are represented as a parse forest. The distinction between a parse tree and a parse forest is that of scale. Both parse trees and parse forests are grammars representing the result of parsing. Think of a forest as merely a set of parse trees.