2015 · 21 citations · 28 references
ComputingComputer ScienceNatural Language ProcessingProgramming LanguagesSyntaxGrammarParsingSyntactic AnalysisSyntactic ParsingSyntax AnalysisSyntax ParsingContext-free Grammar ParsingContext-free GrammarsLanguage ParsingOperator Precedence GrammarOperator Precedence ParsingParser GeneratorsParsing AlgorithmsParsing With Context-free Grammars
Despite the long history of research in parsing, constructing parsers for real programming languages remains a difficult and painful task. In the last decades, different parser generators emerged to allow the construction of parsers from a BNF-like specification. However, still today, many parsers are handwritten, or are only partly generated, and include various hacks to deal with different peculiarities in programming languages. The main problem is that current declarative syntax definition techniques are based on pure context-free grammars, while many constructs found in programming languages require context information. In this paper we propose a parsing framework that embraces context information in its core. Our framework is based on data-dependent grammars, which extend context-free grammars with arbitrary computation, variable binding and constraints. We present an implementation of our framework on top of the Generalized LL (GLL) parsing algorithm, and show how common idioms in syntax of programming languages such as (1) lexical disambiguation filters, (2) operator precedence, (3) indentation-sensitive rules, and (4) conditional preprocessor directives can be mapped to data-dependent grammars. We demonstrate the initial experience with our framework, by parsing more than 20000 Java, C#, Haskell, and OCaml source files.
28
Yacc : Yet Another Compiler Compiler
S. C. Johnson, Murray Hill · 1978 · 1.2K citations
An efficient context-free parsing algorithm
Jay Earley · Communications of the ACM · 1970 · 817 citations · Full text
On the translation of languages from left to right
Donald E. Knuth · Information and Control · 1965 · 792 citations
The next 700 programming languages
P. J. Landin · Communications of the ACM · 1966 · 581 citations · Full text