Reference. Deterministic regular languages

Anne Bruggemann-Klein, Derick Wood · STACS · 1992 · parsing · DOI
The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called content models and they are based on regular expressions. The allowable regular expressions are those that are “unambiguous” as defined by the standard. Unfortunately, the standard’s use of the term “unambiguous” does not correspond to the two well known notions, since not all regular languages are denoted by “unambiguous” expressions. Furthermore, the standard’s definition of “unambiguous” is somewhat vague. Therefore, we provide a precise definition of “unambiguous expressions” and rename them deterministic regular expressions to avoid any confusion. A regular expression E is deterministic if the canonical 𝜀-free finite automaton 𝑀𝐸 recognizing L(E) is deterministic. A regular language is deterministic if there is a deterministic expression that denotes it. We give a Kleene-like theorem for deterministic regular languages and we characterize them in terms of the structural properties of the minimal deterministic automata recognizing them. The latter result enables us to decide if a given regular expression denotes a deterministic regular language and, if so, to construct an equivalent deterministic expression.

Cite
Cite as @bruggemannkleinwood (helia, typst) · \cite{bruggemannkleinwood} (LaTeX)
BibTeX
bibtex · 14 lines
@InProceedings{bruggemannkleinwood,
author="Br{\"u}ggemann-Klein, Anne
and Wood, Derick",
editor="Finkel, Alain
and Jantzen, Matthias",
title="Deterministic regular languages",
booktitle="STACS 92",
year="1992",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="173--184",
abstract="The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called content models and they are based on regular expressions. The allowable regular expressions are those that are ``unambiguous'' as defined by the standard. Unfortunately, the standard's use of the term ``unambiguous'' does not correspond to the two well known notions, since not all regular languages are denoted by ``unambiguous'' expressions. Furthermore, the standard's definition of ``unambiguous'' is somewhat vague. Therefore, we provide a precise definition of ``unambiguous expressions'' and rename them deterministic regular expressions to avoid any confusion. A regular expression E is deterministic if the canonical $\epsilon$-free finite automaton Merecognizing L(E) is deterministic. A regular language is deterministic if there is a deterministic expression that denotes it. We give a Kleene-like theorem for deterministic regular languages and we characterize them in terms of the structural properties of the minimal deterministic automata recognizing them. The latter result enables us to decide if a given regular expression denotes a deterministic regular language and, if so, to construct an equivalent deterministic expression.",
isbn="978-3-540-46775-5"
}
hayagriva YAML (typst)
yaml · 20 lines
bruggemannkleinwood:
  type: article
  title: Deterministic regular languages
  author:
  - Brüggemann-Klein, Anne
  - Wood, Derick
  date: 1992
  editor:
  - Finkel, Alain
  - Jantzen, Matthias
  page-range: 173-184
  serial-number:
    isbn: 978-3-540-46775-5
  abstract: The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called content models and they are based on regular expressions. The allowable regular expressions are those that are ``unambiguous'' as defined by the standard. Unfortunately, the standard's use of the term ``unambiguous'' does not correspond to the two well known notions, since not all regular languages are denoted by ``unambiguous'' expressions. Furthermore, the standard's definition of ``unambiguous'' is somewhat vague. Therefore, we provide a precise definition of ``unambiguous expressions'' and rename them deterministic regular expressions to avoid any confusion. A regular expression E is deterministic if the canonical $\\epsilon$-free finite automaton Merecognizing L(E) is deterministic. A regular language is deterministic if there is a deterministic expression that denotes it. We give a Kleene-like theorem for deterministic regular languages and we characterize them in terms of the structural properties of the minimal deterministic automata recognizing them. The latter result enables us to decide if a given regular expression denotes a deterministic regular language and, if so, to construct an equivalent deterministic expression.
  parent:
    type: proceedings
    title: STACS 92
    publisher:
      name: Springer Berlin Heidelberg
      location: Berlin, Heidelberg
Download: bruggemannkleinwood.bib · bruggemannkleinwood.yml
Cited by (3)

flap: A Deterministic Parser with Fused Lexing yallop-2023-flapPLDI · 2023
Lexers and parsers are typically defined separately and connected by a token stream. This separate definition is important for modularity and reduces the potential for parsing ambiguity. However, materializing tokens as data structures and case-switching on tokens comes with a cost. We show how to fuse separately-defined lexers and parsers, drastically improving performance without compromising modularity or increasing ambiguity. We propose a deterministic variant of Greibach Normal Form that ensures deterministic parsing with a single token of lookahead and makes fusion strikingly simple, and prove that normalizing context free expressions into the deterministic normal form is semantics-preserving. Our staged parser combinator library, flap, provides a standard interface, but generates specialized token-free code that runs two to six times faster than ocamlyacc on a range of benchmarks.
PDF · DOI · arXiv · pldb

Zippy LL(1) parsing with derivatives EdelmannZippy2020PLDI · 2020
In this paper, we present an efficient, functional, and formally verified parsing algorithm for LL(1) context-free expressions based on the concept of derivatives of formal languages. Parsing with derivatives is an elegant parsing technique, which, in the general case, suffers from cubic worst-case time complexity and slow performance in practice. We specialise the parsing with derivatives algorithm to LL(1) context-free expressions, where alternatives can be chosen given a single token of lookahead. We formalise the notion of LL(1) expressions and show how to efficiently check the LL(1) property. Next, we present a novel linear-time parsing with derivatives algorithm for LL(1) expressions operating on a zipper-inspired data structure. We prove the algorithm correct in Coq and present an implementation as a part of Scallion, a parser combinators framework in Scala with enumeration and pretty printing capabilities.
DOI · pldb

A typed, algebraic approach to parsing krishnaswami_typed_2019PLDI · 2019
In this paper, we recall the definition of the context-free expressions (or µ-regular expressions), an algebraic presentation of the context-free languages. Then, we define a core type system for the context-free expressions which gives a compositional criterion for identifying those context-free expressions which can be parsed unambiguously by predictive algorithms in the style of recursive descent or LL(1). Next, we show how these typed grammar expressions can be used to derive a parser combinator library which both guarantees linear-time parsing with no backtracking and single-token lookahead, and which respects the natural denotational semantics of context-free expressions. Finally, we show how to exploit the type information to write a staged version of this library, which produces dramatic increases in performance, even outperforming code generated by the standard parser generator tool ocamlyacc.
DOI · pldb
Cites 12 works (1 here)
With notes (1)

Derivatives of Regular Expressions brzozowskiDerivativesRegularExpressions1964JACM · 1964
Kleene’s regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate) on sets of sequences. Word descriptions of problems can be more easily put in the regular expression language if the language is enriched by the inclusion of other logical operations. However, in the problem of converting the regular expression description to a state diagram, the existing methods either cannot handle expressions with additional operators, or are made quite complicated by the presence of such operators.In this paper the notion of a derivative of a regular expression is introduced and the properties of derivatives are discussed. This leads, in a very natural way, to the construction of a state diagram from a regular expression containing any number of logical operators.
DOI
External (11)
bruggemannkleinwood reference entries/refs/bruggemannkleinwood/bruggemannkleinwood.hel