Concept

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. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser. Unlike CFGs, PEGs cannot be ambiguous; a string has exactly one valid parse tree or none. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. PEGs are well-suited to parsing computer languages (and artificial human languages such as Lojban), but not natural languages where the performance of PEG algorithms is comparable to general CFG algorithms such as the Earley algorithm. Formally, a parsing expression grammar consists of: A finite set N of nonterminal symbols. A finite set Σ of terminal symbols that is disjoint from N. A finite set P of parsing rules. An expression eS termed the starting expression. Each parsing rule in P has the form A ← e, where A is a nonterminal symbol and e is a parsing expression. A parsing expression is a hierarchical expression similar to a regular expression, which is constructed in the following fashion: An atomic parsing expression consists of: any terminal symbol, any nonterminal symbol, or the empty string ε. Given any existing parsing expressions e, e1, and e2, a new parsing expression can be constructed using the following operators: Sequence: e1 e2 Ordered choice: e1 / e2 Zero-or-more: e* One-or-more: e+ Optional: e? And-predicate: &e Not-predicate: !e Group: (e) Operator priorities are as follows, based on Table 1 in: The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered.

Official source

https://en.wikipedia.org/wiki/Parsing_expression_grammar

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 courses (26)

CS-214: Software construction

Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and fundamental software construction concepts (reusability, abstr ...

CS-438: Decentralized systems engineering

A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the engineering of their own decentralized system featuring messaging, file sha ...

CS-420: Advanced compiler construction

Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time system for a simple functional programming language. ...

Related lectures (32)

Foundations of Software: Modeling Programming Languages

Covers the mathematical study of program behaviors, parsing, domain-specific languages, and powerful tools for language design.

Syntax Trees: Parse vs AST

Explains syntax trees, parse vs AST, while language syntax, AST classes, and grammar ambiguities.

LL(1) Parsing

Covers LL(1) parsing, formalization, automation, constraints, and parsing tables.

Related publications (23)

From Patterns to Programs: A Formal Model for Repetitions of Hierarchical Relations in Sequential Data

Patterns are fundamental to human cognition: humans recognize regularities that recur across contexts and levels of abstraction. Some regularities are not properties of raw observations but of the underlying generative logic that explains them. We study this class of regularities, structural repeats, which arise from the recurrence of hierarchical relations within a sequence. We present a formal model for recognizing structural repeats based on a weighted-deduction system that searches for compact programs.

Springer2026

Automatic Layout of Railroad Diagrams

Railroad diagrams (also called “syntax diagrams”) are a common, intuitive visualization of grammars, but limited tooling and a lack of formal attention to their layout mostly confines them to hand-drawn documentation. We present the first formal treatment of railroad diagram layout along with a principled, practical implementation. We characterize the problem as compiling a diagram language (specifying conceptual components and how they connect and compose) to a layout language (specifying basic graphical s

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2026

Formally Verified Linear-Time Invertible Lexing

We present ZipLex, a verified framework for invertible linear-time lexical analysis following the longest match (maximal munch) semantics. Unlike past verified lexers that focus only on satisfying the semantics of regular expressions and the longest match property, ZipLex also guarantees that lexing and printing are mutual inverses. Thanks to verified memoization, it also ensures that the lexical analysis of a string is linear in the size of the string. Our design and implementation rely on two sets of idea

Springer Science and Business Media Deutschland GmbH2026

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.

Official source

https://en.wikipedia.org/wiki/Parsing_expression_grammar

About this result

Ontological neighbourhood

Computer engineering

Computer programming: Compilers

Related courses (26)

CS-214: Software construction

CS-438: Decentralized systems engineering

CS-420: Advanced compiler construction

Related lectures (32)

Foundations of Software: Modeling Programming Languages

Covers the mathematical study of program behaviors, parsing, domain-specific languages, and powerful tools for language design.

Syntax Trees: Parse vs AST

Explains syntax trees, parse vs AST, while language syntax, AST classes, and grammar ambiguities.

LL(1) Parsing

Covers LL(1) parsing, formalization, automation, constraints, and parsing tables.

Related publications (23)

From Patterns to Programs: A Formal Model for Repetitions of Hierarchical Relations in Sequential Data

Springer2026

Automatic Layout of Railroad Diagrams

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2026

Formally Verified Linear-Time Invertible Lexing

Springer Science and Business Media Deutschland GmbH2026

Related people (9)

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Martin Odersky heads the programming research group at EPFL. His research interests cover fundamental as well as applied aspects of programming languages. They include semantics, type systems, programming language design, and compiler construction. The main focus if his work lies in the integration of object-oriented and functional programming. His research thesis is that the two paradigms are just two sides of the same coin and should be unified as much as possible. To prove this he has experimented a number of language designs, from Pizza to GJ to Functional Nets. He has also influenced the development of Java as a co-designer of Java generics and as the original author of the current javac reference compiler. His current work concentrates on the Scala programming language, which unifies FP and OOP, while staying completely interoperable with Java and .NET. Martin Odersky got his doctorate from ETHZ, in 1989. He held research positions at the IBM T.J. Watson Research Center from 1989 and at Yale University from 1991. He was then a professor at the University of Karlsruhe from 1993 and at the University of South Australia from 1997. He joined EPFL as full professor in 1999. He is associate editor of the Journal of Functional Programming and member of IFIP WG 2.8. He was conference chair for ICFP 2000, and program chair for ECOOP 2004 as well as ETAPS/CC 2007.

Michael Christoph Gastpar

Michael Gastpar is a (full) Professor at EPFL. From 2003 to 2011, he was a professor at the University of California at Berkeley, earning his tenure in 2008. He received his Dipl. El.-Ing. degree from ETH Zürich, Switzerland, in 1997 and his MS degree from the University of Illinois at Urbana-Champaign, IL, USA, in 1999. He defended his doctoral thesis at EPFL on Santa Claus day, 2002. He was also a (full) Professor at Delft University of Technology, The Netherlands. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He is a Fellow of the IEEE. He is the co-recipient of the 2013 Communications Society & Information Theory Society Joint Paper Award. He was an Information Theory Society Distinguished Lecturer (2009-2011). He won an ERC Starting Grant in 2010, an Okawa Foundation Research Grant in 2008, an NSF CAREER award in 2004, and the 2002 EPFL Best Thesis Award. He has served as an Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory (2008-11), and as Technical Program Committee Co-Chair for the 2010 International Symposium on Information Theory, Austin, TX.

Emre Telatar

I. Emre Telatar received the B.Sc. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1986. He received the S.M. and Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1988 and 1992 respectively. In 1992, he joined the Communications Analysis Research Department at AT&T Bell Laboratories (later Lucent Technologies), Murray Hill, NJ. He has been at the EPFL since 2000. Emre Telatar was the recipient of the IEEE Information Theory Society Paper Award in 2001. He was a program co-chair for the IEEE International Symposium on Information Theory in 2002, and associate editor for Shannon Theory for the IEEE Information Theory Transactions from 2001 to 2004. He was awarded the EPFL Agepoly teaching prize in 2005. Emre Telatar's research interests are in communication and information theories.

Sabine Süsstrunk

Prof. Dr. Sabine Süsstrunk leads the Image and Visual Representation Lab in the School of Computer and Communication Sciences (IC) at EPFL since 1999. From 2015-2020, she was also the first Director of the Digital Humanities Institute (DHI), College of Humanities (CdH). Her main research areas are in computational photography, computational imaging, color image processing and computer vision, machine learning, and computational image quality and aesthetics. Sabine has authored and co-authored over 200 publications, of which 7 have received best paper/demo awards, and holds over 10 patents. Sabine served as chair and/or committee member in many international conferences on image processing, computer vision, and image systems engineering. She is President of the Swiss Science Council SSC, Founding Member and Member of the Board (President 2014-2018) of the EPFL-WISH (Women in Science and Humanities) Foundation, Member of the Board of the SRG SSR (Swiss Radio and Television Corporation), and Member of the Board of Largo Films. She received the IS&T/SPIE 2013 Electronic Imaging Scientist of the Year Award for her contributions to color imaging, computational photography, and image quality, and the 2018 IS&T Raymond C. Bowman and the 2020 EPFL AGEPoly IC Polysphere Awards for excellence in teaching. Sabine is a Fellow of IEEE and IS&T.

Related units (2)

Laboratory for Automated Reasoning and Analysis

Programming Methods Laboratory 1

Related concepts (14)

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.

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.

Bottom-up parsing

In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leaving the highest-level overall structure to last. The bottom-up name comes from the concept of a parse tree, in which the most detailed parts are at the bottom of the upside-down tree, and larger structures composed from them are in successively higher layers, until at the top or "root" of the tree a single unit describes the entire input stream.

Related exercises (4)

Excitation of a vertical harmonic oscillator

A mass m is suspended on a spring of natural length l₀ and of elastic constant k. The spring is attached to a piston. The vertical motion of the piston is described by the equation s(t)u2004=u2004s₀cosu2006(ωt)xa0.

Give explicit expressions for the external forces and determine the equation of motion.
Show that the equation of motion can be recast as, $\ddot{x}\left(t\right) + c_1\,x\left(t\right) = c_1\,s\left(t\right)\ ,$ where x(t)u2004=u2004z(t)u2005+u2005c₂ with z(t) the vertica

Oscillator on an inclined plane

A material point of mass m is required to move along a line with an angle of inclination α with respect to a horizontal line. There is no friction. The point mass is attached to a spring of natural length l₀ and of constant k.

Give explicit expressions for the forces.
Determine the equation of motion.
What is the oscillation period ?

Frame, coordinates and system: We take the inclined plane as frame of reference and choose the coordinate e_(x) parallel to the inclined plane oriented towards

Rotation on a two-blade helix

A homogeneous rod of length L and mass M rotates in a vertical plane around the horizontal axis OG at constant angular velocity ψ̇u2004=u2004ψ̇u2006e₃. The axis OG rotates around the vertical axis ẑ at constant angular velocity ϕ̇u2004=u2004ϕ̇u2006e_(z). The moment of inertia of the rod with respect to its axis is I_(G∥) and the torques perpendicular to the axis of the rod passing through G are I_(G⊥). The distance |OG|u2004=u2004R.

Show that the angular momentum L_(G) is expressed in the principal