UNIX: A History and a Memoir by Brian Kernighan

Author:Brian Kernighan [Kernighan, Brian]
Language: eng
Format: epub
Published: 2019-10-28T06:00:00+00:00

CHAPTER 5: SEVENTH EDITION

91

The first part of the compilation process is to parse the program, that is, to determine its syntactic structure by recognizing names, constants, function definitions, control flow, expressions, and the like, so that subsequent processing can attach suitable semantics.

Today, writing a parser for a programming language is well-understood technology, but in the early 1970s it was an active research area, focused on creating programs that would convert the grammar rules of a language into an efficient parser for programs written in that language. Such parser-generator programs were also known as “compiler-compilers,” since they made it possible to generate the parser for a compiler mechanically. Typically they created a parser and also provided a way to execute code when particular grammar constructs were encountered during parsing.

Yacc

In 1973, Steve Johnson (Figure 5.1), with language-theory help from Al Aho, created a compiler-compiler that he called YACC (henceforth Yacc). A comment from Jeff Ullman inspired the name, which stands for “yet another compiler-compiler,” suggesting that it was not the first such program.

Figure 5.1:

Steve Johnson, ∼1981 (Courtesy of Gerard Holzmann)

92 CHAPTER 5: SEVENTH EDITION

A Yacc program consists of grammar rules for the syntax of a language, and semantic actions attached to the rules so that when a particular grammatical construction is detected during parsing, the corresponding semantic action can be performed. For example, in pseudo-Yacc, part of the syntax of arithmetic expressions might be:

expression := expression + expression expression := expression * expression and the corresponding semantic actions might be to generate code that would add or multiply the results of the two expressions together and make that the result. Yacc converts this specification into a C program that parses input and performs the semantic actions as the input is being parsed.

Normally a compiler writer would have to write more complicated rules to handle the fact that multiplication has higher precedence than addition (that is, multiplications are done before additions), but in Yacc, operator precedence and associativity can be specified by separate declarations rather than additional grammar rules, which is a huge simplification for non-expert users.

Steve himself used Yacc to create a new “portable C compiler” (PCC) that had a common front end for parsing the language and separate back ends for generating code for different computer architectures. Steve and Dennis also used PCC in their implementation of Unix for the Interdata 8/32, as described in Section 6.5.

PCC had other uses as well. As Steve recalls,

“An unexpected spin-off from PCC was a program called Lint. It would read your program and comment on things that were not portable, or just plain wrong, like calling a function with the wrong number of arguments, inconsistent sizes between definition and use, and so on.

Since the C compiler only looked at one file at a time, Lint quickly became a useful tool when writing multi-file programs. It was also useful in enforcing standards when we made V7 portable, things like looking for system calls whose error return was −1 (Version 6) instead of null (V7). Many

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.