Yacc

- Developed by Stephen C. Johnson at Bell Labs / AT&T in the early 1970s - Created to insert an exclusive or operator into a B language compiler - Directed by colleague Al Aho to Donald Knuth's work on LR parsing - Influenced by McIlroy's TMG compiler-compiler and named in reference to TMG - Originally written in B programming language, later rewritten in C by Alan Snyder - Yacc takes a grammar with C code snippets as input - Outputs a shift-reduce parser in C that executes code snippets associated with each rule - Actions involve constructing parse trees - Special identifiers like $$, $1, and $3 refer to items on the parser's stack - Full syntactic analysis typically requires an external lexical analyzer for tokenization - Yacc was popular and widely used, but has been replaced by newer programs like Berkeley Yacc, GNU Bison, etc. - Implemented the first versions of languages like AWK, C++, eqn, and Pic - Used to implement the Portable C Compiler and parsers for various languages - Rewritten for other languages like OCaml, Ratfor, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lisp, and Erlang - Berkeley Yacc became more popular than AT&T Yacc due to performance and lack of reuse restrictions - Compiler-compiler - hoc (programming language) - The A-Z of Programming Languages: YACC - Lex & yacc by John Levine - Flex & bison by John Levine - Stephen Curtis Johnson: Geek of the Week - The Development of the C Language