LL(1) Parsing

This lecture introduces LL(1) parsing, a parsing technique that can be easily implemented manually based on the grammar, showing the correspondence between grammar and code through concatenation, alternative, repetition, and nonterminal recursive procedures. It covers the formalization and automation of LL(1) parsers, rewriting grammars for recursive descent parsers, and the computation of 'first' and 'nullable' sets. The lecture also discusses the rules and constraints for LL(1) grammars, the iterative solution for computing constraints, and the LL(1) parsing table. Examples and exercises are provided to illustrate the concepts and algorithms.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (3)

Related concepts (40)

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

Recursive descent parser

In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. A predictive parser is a recursive descent parser that does not require backtracking.

Parsing expression grammar

In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.

Top-down parsing

Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis.

LR parser

In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers, and GLR parsers. LR parsers can be generated by a parser generator from a formal grammar defining the syntax of the language to be parsed. They are widely used for the processing of computer languages.

Parser combinator

In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully. Parser combinators enable a recursive descent parsing strategy that facilitates modular piecewise construction and testing.

Parsing: CYK Algorithm

Explores formal grammars, parsing algorithms, CYK algorithm efficiency, and syntactic correctness in Natural Language Processing.

CYK Parsing Algorithm for General Grammars CS-320: Computer language processing

Introduces the CYK parsing algorithm for context-free grammars, explaining its handling of ambiguity and importance in parsing general grammars.

CYK algorithm

Introduces the CYK algorithm for efficient syntactic analysis using chart parsing and discusses its complexity and bottom-up parsing technique.