Lecture

Context-Free Grammars

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture introduces context-free grammars as a formalism more expressive than finite automata and regular expressions, allowing the description of context-free languages. The instructor explains the equivalence between pushdown automata and context-free grammars, detailing the components and transitions of pushdown automata. The lecture covers the definition of context-free grammars, including terminals, non-terminals, and rules. It explores the concept of context-free languages and how to verify if a word belongs to a grammar's language using algorithms like the CYK algorithm. Additionally, the lecture delves into the pumping lemma for context-free languages, demonstrating how to find a repeated substring within a language. The hierarchy of grammar types is discussed, highlighting the restrictions and expressiveness of different grammar levels, leading up to Type 0 grammars, which have no restrictions on rule application.

Official source

Ontological neighbourhood

Computer engineering

Computer programming: Compilers

Related concepts (32)

Context-free language

In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars. Different context-free grammars can generate the same context-free language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar by comparing multiple grammars that describe the language.

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form with a single nonterminal symbol, and a string of terminals and/or nonterminals ( can be empty). Regardless of which symbols surround it, the single nonterminal on the left hand side can always be replaced by on the right hand side.

Deterministic context-free language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs. DCFLs are of great practical interest, as they can be parsed in linear time, and various restricted forms of DCFGs admit simple practical parsers.

Formal grammar

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for such strings in a formal language. Formal language theory, the discipline that studies formal grammars and languages, is a branch of applied mathematics.

Deterministic context-free grammar

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however. DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator.

Related lectures (64)

Regular Expressions (Recap)

Covers the fundamentals of regular expressions and includes exercises on defining languages.

Finite Automata: Basics

Introduces the basics of finite automata, including deterministic and non-deterministic types, regular expressions, and acceptance criteria.

CYK Parsing Algorithm for General Grammars

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

Finite Automata: Recap

Covers the fundamentals of finite automata and formal languages.

Grammars and Parsers: An Overview of Language Processing