A piece of software which reads in gramatical tokens and performs actions associated with those tokens. Parsers can be written with bison or by hand. Parsers usually rely heavily on a lexer as well.

A parser is a program that recognizes (parses) a language. In compiling (or interpreting) a program, a parser typically accepts as input a stream of tokens generated by a lexical analyzer. The parser then transforms this stream into a representation of the program it recognized. The output is usually some intermediate format, such as some other high level language, or perhaps an abstract syntax tree, though in some cases actual machine code is generated.

program text          tokens
-------------> lexer  -------> parser ---> output

The lexer and parser combination of a compiler is often called its front-end. Parsers can be built by hand, or they can be built using one of several available parser-generators, such as yacc/bison, or ANTLR. Typically in using these tools, the language to be recognized is written in some extended form of BNF, along with embedded "actions" that tells the parser what to do when a BNF rule is recognized.

yacc is an LALR(1) parser generator, while ANTLR is an LL(k) parser generator. This means that these tools, in the interest of efficiency, can be specified only to accept a subset of context free grammars.

Pars"er (?), n.

One who parses.


© Webster 1913.

Log in or register to write something here or to contact authors.