Discover published sets by community

Recursive descent parsing is a top-down parsing technique in which each non-terminal in a CFG is implemented by a function which attempts to match the input sentence with the productions. It can naturally handle left recursion and is easy to implement.

Shift-Reduce parsers incrementally transform the input string into the syntax tree by applying 'shift' actions to advance in the input and 'reduce' actions to fold parts of the input into non-terminals via reverse application of production rules.

Top-Down parsing starts from the start symbol and attempts to rewrite it to the given sentence. It explores the parsing possibilities in a depth-first manner, which can be done using a recursive descent parser or a predictive parser.

The CYK algorithm is a bottom-up parsing technique that applies dynamic programming for parsing strings in CNF (Chomsky Normal Form) grammars. It fills a parsing table in a bottom-up fashion which can also be used to parse ambiguous grammars.

Left-Corner parsing is a hybrid parsing method that combines both top-down and bottom-up strategies. It begins with a top-down prediction and waits until a left-corner of the predicted category is found before confirming the prediction.

Bottom-Up parsing begins with the input sentence and attempts to reduce it to the start symbol of a CFG by reversing the production rules. Shift-reduce parsing, including the LR parser family, is a common bottom-up approach.

Predictive parsing is a form of Top-Down parsing without backtracking. Parsing decisions are made based on the current input symbol and a lookahead. LL grammars are a type of grammar that is suitable for predictive parsing.

CFGs consist of a set of recursive rewriting rules used to generate patterns of strings. They are widely used for the syntax of programming languages and the analysis of natural language sentences due to their balance of expressivity and computational efficiency.

Parse trees are hierarchical tree structures that represent the syntactic structure of a string according to a CFG. Each node corresponds to a symbol which is either a terminal or a non-terminal in the grammar.

The Earley parser is an algorithm that can parse all context-free languages. It uses dynamic programming to efficiently handle ambiguous grammars. It's characterized by its parsing tables and the ability to handle any CFG.

HPSG is a highly lexicalized, constraint-based grammar that focuses on the properties of the 'head' of a phrase. It's used for deriving detailed syntactic structures and incorporates both syntactic and semantic information.