Parsing

From TunesWiki

The term for the process of turning an input stream into an Abstract Syntax Tree. Parsing generally depends on the complexity of the grammar or syntax, and in the most general cases can require a Turing-complete program, i.e. its own programming language.

References

• Wikipedia has some good info on Parsing.
• Djikstra's Shunting yard algorithm looks like a nice combination of simplicity & efficiency, with the added benefit that syntax can be modified at runtime.
• The book, available online, Parsing Techniques - A Practical Guide by Dick Grune and Ceriel J.H. Jacobs.
• The book, available online, Prolog Parsers - Parsing techniques in Prolog, by Klaus von Bremen.
• A Compact Guide to Lex & Yacc.
• At compilertools.net:
  • The Lex & Yacc Page.
  • The Catalog of Compiler Construction Tools: freeware and commercial resources for compiler writers.
• Parser and Scanner Generators.
• Concurrent, Object-Oriented Natural Language Parsing: The ParseTalk Model (.pdf, .ps).
• Let's Build a Compiler, by Jack Crenshaw, Ph.D. - an introduction to program translators, using a simplified approach inspired by Small C.
• Introduction to Syntax Directed Parsing.
• A paper higly relevant for Meta-Translator SubProject:

  Current Parsing Techniques in Software Renovation Considered Harmful (.ps), by Mark van den Brand, Alex Sellink, Chris Verhoef.

  Abstract. We evaluate the parsing technology used by people working in the reengineering industry. We discuss parser generators and complete systems like Yacc, TXL, TAMPR, REFINE, CobolTransformer, COSMOS, and ASF_SDF. We explain the merits and drawbacks of the various techniques. We conclude that current technology may cause problems for the reengineering industry and that modular and/or compositional parsing techniques are a possible solution.

  See also metafront.

• [ MIA ] Lex & Yacc Tutorial (a copy).

Implementations

• ANTLR ANother Tool for Language Recognition, FKA PCCTS, a framework for constructing recognizers, compilers, and translators.
• Attribute Grammars home page.
• basil (SourceForge project) a parsing and modeling environment for working with, code in, and integrate any computer language.
• The BNF Converter a BNF-based compiler construction tool written for Haskell.
• C++ Compiler Compiler (CppCC) (SourceForge project) an object-oriented scanner and LL(k) parser generator. It aims to replace LEX&YACC for those who write C++ applications that involve parsing.
• Compiler Generation Tools for C#.
• At compilertools.net:
  • ACCENT - A Compiler Compiler for the Entire Class of Context-Free Languages.
  • The GENTLE Compiler Construction System.
• CTool a C lexer/parser with a symbol table.
• ddgen by Kjell Post, a parser generator for dynamic operator languages.
• Dendra (old link MIA) Lisp style syntax parsing and printing code.
• dparser (freshmeat entry) a scannerless GLR parser generator based on the Tomita algorithm.
• Essence, an LR parser generator for Scheme.
• Functional Parsers.
• Gray a parser generator in Forth.
• ipars Incremental scanner/PARSer.
• lambdayacc Lambda Prolog Parser Generator.
• language machine - recognise and substitute unrestricted grammatical patterns with variable bindings.
• Lextools: a package of tools for creating weighted finite-state transducers from high-level linguistic descriptions.
• lfg a parser for an LFG-like grammar formalism for Scheme.
• locos an OO framework for building parsers and other language processing tools.
• lrc a system for generating efficient incremental attribute evaluators, used to generate language based editors and other advanced interactive environments.
• metafront, a tool for specifying syntactic transformations between languages, defined by context-free grammars, which uses specificity parsing, that is designed to support gradual extensions of a grammar.
• O2C2 – Object Oriented Compiler Construction, generate a set of classes for a recursive descent LL (k)-based parser from a given syntactic specification of the language expressed in EBNF notation.
• Olex (SourceForge project) a LL(1) parser generator for C++.
• Plex a Python module for constructing lexical analysers/scanners.
• Parsec, a fast combinator parser.
• Ratatosk ftp directory (Ratatosk.tar.Z), a lexer/parser generator for Gofer (Haskell) by Torben Ægidius Mogensen.
• REGEX/CLAWK/LEXER Packages (CLiki entry) regex matcher/interesting bits of AWK/lexer-generator macro.
• The SLK Parser Generator.
• SHACC Shaggy's Homebrew Alternative Compiler Compiler, YACC replacement.
• SLG Simple Language Generator, stochastic context-free grammar tool.
• SPARK Scanning, Parsing and Rewriting Kit.
• T-Gen - The Parser Generator for Visualworks (ftp) a Smalltalk parser generator.
• TGrep2 the next-generation search engine for parse trees.
• Yacc to LaTeX (y2l) Yacc to Latex, yacc grammar description file as input, EBNF grammar in latex as output.
• Yapps Yet Another Python Parser System.