YACC AND Lex

There are two traditional UNIX utilities named yacc and lex that enable you to create compilers for computer languages that you design yourself. Mike Lesk developed the original version of lex around 1975 at the AT&T Bell Labs. It can help you make lexical analysers, and its main job is to break up an input stream into usable elements, which are called tokens. Lexical analysers are naïve tools that do not deal with the true meaning of the tokens – this is the job of a parser such as yacc or bison. The lexical analysis phase usually eliminates all blanks, because apart from helping you separate tokens they have no other use. The lex utility has been subsequently been completely replaced by flex.

The name ‘yacc’ is an acronym for Yet Another Compiler Compiler, because yacc is a utility for creating compilers for programming languages. In computer science terminology, yacc is a parser generator. This means that it gets a grammar of a programming language as its input and generates the source code of a parser as its output. It is the job of the parser to determine the meaning of each token and whether a variable has a valid name or not, and maybe reject it and generate error messages.

Strictly speaking, yacc is a LALR parser generator – a software tool that reads a BNF grammar and creates an LALR parser. The LALR parser is capable of separating and analysing a text according to a set of production rules for left-to-right (LR). The production rules are specified by a formal grammar. Yacc has been replaced by bison.