2011 · 37 citations · 13 references
ComputingComputer ScienceProgramming LanguagesSyntaxTheory Of ComputationFunctional ProgrammingGrammarParsingSyntactic ParsingSyntax AnalysisSyntax ParsingContext-free Grammar ParsingContext-free GrammarsExpression ParsingParser CombinatorsParsing AlgorithmsParsing TheoryParsing With Context-free GrammarsRegular Expressions
We present a functional approach to parsing unrestricted context-free grammars based on Brzozowski's derivative of regular expressions. If we consider context-free grammars as recursive regular expressions, Brzozowski's equational theory extends without modification to context-free grammars (and it generalizes to parser combinators). The supporting actors in this story are three concepts familiar to functional programmers - laziness, memoization and fixed points; these allow Brzozowski's original equations to be transliterated into purely functional code in about 30 lines spread over three functions.
13
Derivatives of Regular Expressions
Janusz Brzozowski · Journal of the ACM · 1964 · 931 citations · Full text
On the translation of languages from left to right
Donald E. Knuth · Information and Control · 1965 · 792 citations
Syntactic Analysis and Operator Precedence
Robert W. Floyd · Journal of the ACM · 1963 · 256 citations · Full text
Language Studies, Computer Science, Computational Linguistics +7