伯克利大学CS164编译原理讲义解析

需积分: 12 58 浏览量更新于2024-07-20 2 收藏 608KB PDF 举报

"ubc cs164编译原理 notes" 这篇文档是保罗·尼尔·希尔芬格在加州大学伯克利分校教授的编译原理课程的讲义，日期为2010年2月10日。内容涵盖了编译器设计的基础知识，包括编译原理的目的、编程语言的历史、编译器需要解决的问题、不同类型的翻译器，以及重点讲解了词法分析。在课程的介绍部分，希尔芬格讨论了开设这门课程的主要目的，不仅是为了让学生理解编程语言的设计和实现，还在于掌握如何将高级语言转换为机器可执行代码。他简述了编程语言的发展历程，从早期的低级语言到现代的高级语言，强调了编译器在其中的关键作用。接着，希尔芬格列举了编译器需要解决的一些问题，如语义分析、语法解析、优化和目标代码生成。他还介绍了不同的翻译器类型，如解释器、编译器、JIT（Just-In-Time）编译器等，以及它们在程序执行中的差异。在词法分析章节，文档详细阐述了这一过程，它是编译器的第一个阶段，负责将源代码分解成一个个称为“标记”（tokens）的基本单元。希尔芬格讲解了简单和扩展的正则表达式，以及如何使用它们来定义标记模式。他还提到了通用目的语言中正则表达式的应用，以及专门为词法分析设计的工具——Flex。在有限状态机（Finite-state Machines，FSMs）部分，希尔芬格区分了确定性和非确定性识别器，并解释了如何将这些 FSM 转换为程序。他探讨了从非确定性有限状态自动机（NFA）到确定性有限状态自动机（DFA）的转换，以及从正则表达式构建FSM的方法。此外，他还指出了理论上的局限性，比如正则表达式无法表示某些复杂的语言结构。最后，文档回顾了Flex的实现细节，包括启动状态和如何处理特殊情况。这部分内容对于实际编写词法分析器是非常实用的指导。这份伯克利大学的CS164编译原理讲义提供了深入的编译器设计理论和实践知识，对于学习编译器构造和理解计算机科学基础的学生来说是一份宝贵的资源。

16 CHAPTER 2. LEXICAL ANALYSIS

• Deterministic ﬁnite-state automata (DFAs) are a subset of ﬁnite-state au-

tomata that are easily converted into programs.

• There exists a trans lation from regular expressions into FSAs.

• There exists a translation from FSAs that happen to be nondeterministic into

DFAs (and hence into programs).

• The total process of conversion from regular expression to program is au-

tomatable. In fact, we’ll be using a couple of h an dy programs: Flex (for

producing scanners written in C or C++) and JFlex (for producing scanners

written in Java). Th ese programs are really compilers themselves, translating

succinct descriptions of programming-language syntax (a piece of it, anyway)

into programs that “execute” these d escriptions to extract tokens from the

input.

2.2 Tokens and Tokenizing

In the context of programming-language translation we use the term token to refer

to an abstraction for the s mallest unit of program text that it is convenient when

describing the syntax of a language. You don’t want them to be too small. The

parsing techniques we’ll use in this class are designed to decide on what to do

next on the basis of the n ext token of input. If tokens are single characters, they

won’t generally contain enough information to make this decision. For example,

suppose a program has seen the characters ‘x+y’ and the next character is a blank.

This is insuﬃcient information to determine whether ‘x+y’ is to be treated as a

subexpression, since if the next non-blank character is ‘*’, then y should be grouped

with wh atever is after the asterisk. The lexer, on the other h and, can ﬁrst eliminate

whitespace, making the decision easier. Another example is ‘x+y’ followed by a

‘+’. Here, the decision depends on whether the character immediately after the ‘+’

is another ‘+’. If the lexer has p reviously grouped all ‘++’s into s ingle tokens, the

decision is easily made, with no ad hoc scanning ahead in special cases. Tokenizing

is thus the process of bridging the gap between the inp ut (made of characters—too

small) and tokens .

As an example, a Java program (a Java source ﬁle) might contain th e phrase

if(i== j)

z = 0; /* No work needed */

else

z= 1;

which a translating program sees as a s equ en ce of characters:

\tif(i== j)\n\t\tz = 0; /* No work needed */\n\telse\n\t\tz= 1;

The job of the scanner is to convert this to a sequence of values such as this:

IF, LPAR, ID("i"), EQUALS, ID("j"), RPAR, ID("z"), ASSIGN,

INTLIT("0"), SEMI, ELSE, ID("z"), ASSIGN, INTLIT("1"), SEMI

2.3. SIMPLE REGULAR EXPRESSIONS 17

Here, the upper-case symbols denote syntactic categories (often intern ally repre-

sented as integers in an actual compiler). The syntactic categories are consumed by

the next stage of the compiler—the parser. When determining the structur e of a

program, it is not particularly important which identiﬁer or integer literal appears

at some point; the important point is that some identiﬁer appears there. Hence,

scanners typically separate the syntactic category from what I’ll call the lexical

value of the token (shown in parentheses), which gives inform ation that the parser

doesn’t need, but later stages of the compiler will. In our example, the lexical value

of an identiﬁer happens to be the lexeme itself—the character strin g constituting

the token.

As you can see from the example, information unnecessary to the rest of the

compiler is ﬁltered out entirely. All the blanks, tabs, newlines, and comments are

gone, so that the little discrepancies in sp acing around the operators are removed.

This is a typical pattern in the translation pr ocess: each stage makes the job of

its successors easier by removing “noise” and guaranteein g that certain errors are

ﬁltered out.

Actually, real scanners don’t entirely do away with whitespace. If it is going

to produce useful error messages, a compiler must keep track of where each token

appears so that it can “point” at the oﬀending part of the program in the original

source ﬁle. Therefore, tokens often contain positional information—but just like

the semantic value, it is separated from other parts of the token so that it can be

referenced only when needed.

If we were bu ilding an actual scanner in Java, our tokens might be represented

by objects with ﬁelds like this:

class Token {

enum SyntacticCategory { IF, LPAR, ID, EQUALS, RPAR, ASSIGN, ... };

SyntacticCategory syntax;

Object value;

Location sourcePosition;

...

}

2.3 Simple Regular Expressions

In formal language theory (as computer scientists practice it, that is), a language

is a just set of strings—namely, all the valid sentences, utterances, or words in that

language. Th is deﬁnition does not really correspond to the normal informal-English

use of the word, but it can be useful for our purposes. The problem of creating a

lexical analyzer is that of writing a program to recognize and extract the valid

tokens making up some input text (or source). Now, we could just treat this as a

Small Matter of Programming, and write a program from scratch that performed

this task. The obvious approach might give you s omething like this (in Java):

int lastChar;

Token readToken () {

do {

lastChar = System.in.read ();

18 CHAPTER 2. LEXICAL ANALYSIS

if (lastChar == -1)

return makeToken (EOF);

} while (Character.isWhitespace (c));

if (lastChar == ’/’) {

lastChar = System.in.read ();

if (lastChar == ’*’) {

Read and discard comment

return readToken ();

} else if (lastChar == ’/’) {

Read and discard //-style comment.

} else

return makeToken (SLASH);

} else if ...

...

}

and so on. This can go on for quite a while and become r ather tedious. I n particular,

verifying that a program such as this in fact matches our notion of what the possible

tokens are is certainly not easy. On the other hand, if you are trying to squeeze

every possible bit of speed out of a lexical analyzer for some reason, you may be

driven to such lengths.

It would be nice if there were a way to describe the possible tokens we’re looking

for directly and to have this description converted into a program automatically,

so th at it is a program that endures the tedium. For lexical analysis, a common

description language for this purpose is the regular expression.

A classical regular expression, R, d escribes a language (set of strings) L(R) (the

language of R), according to the following recursive deﬁnition:

• The empty string, ǫ, is a regular expression, denoting the set containing just

the empty string (L(ǫ) = {""}).

• Any single character, c, is a regular expression, denoting the set containing

just the on e-character string containing c (L(c) = {"c"}).

• Concatenation: If R

and R

are two regular expressions deﬁned by th ese

rules, then R

is a regular expression denoting the set L(R

) = {s

| s

∈

L(R

) and s

∈ L(R

)}.

• Union: If R

and R

are two regular expressions deﬁned by these rules, then

is a regular expression denoting the set L(R

) = L(R

) ∪ L(R

• Closure: If R is a regular expression deﬁned by these rules, then R∗ is a regular

expression

, denoting the set L(R∗) = L(ǫ) ∪ L(R) ∪ L(RR) ∪ L(RR R) ∪ · · ·

(the concatenation of zero or more strings, each from L(R)).

For convenience, we often augment these with

The ‘*’ operator is known as the Kleene star, after the late St ephen C. Kleene, and pronounced

(in America, anyway) like “Claynee”.

2.4. STANDARD EXTENSIONS TO REGULAR EXPRESSIONS 19

• Non-reﬂexive closure : If R is a regular expression deﬁned by these rules, then

is a shorthand for RR∗ (the concatenation of one or more s tr ings, each

from L(R)).

• Optional: I f R is a regular expression deﬁned by these rules, then R? is a

shorthand for R|ǫ.

and the regular-expression analyzers we’ll talk about all allow standard shorthan ds

for unions of single-character tokens:

• The expression [c

· · ·] is short for c

| · · ·. The expression a-b in place

of one of the c

is short for the list of all one-character strings containing

characters between a and b, inclusive, in whatever character collating sequence

you are using (so [f-i] is the same as [fghi]).

• The expression [^c

· · ·] is short for d

| · · ·, where the d

are all characters

that are not included among the c

• The expression ‘.’ generally means “the union of all single ch aracter strings

not including line-terminating characters.”

Normally, the closures and optional operators group more strongly than concate-

nation, which groups more strongly than union, and we use parenth eses to clarify

or disambiguate, so that “ab—cd*” is equivalent to “(ab)—(c(d*)).” When writing

regular expressions that programs will actually act on, there is also a tedious set

of rules concerning escape s equ en ces, so that we can describe s tr ings that include

characters such ‘*’, ‘+’, ‘|’, etc.

This notation easily describes typical tokens in programming languages and

many other simple strings as well. Here are a few examples:

Expression

Description

[-+/*=;,:()%^!@&|~\[\]] Valid one-character tokens in Java (the square brackets are

“escaped” with a backslash to indicate that they are to be

interpreted as ordinary characters).

[-+/*^\%|&]=

All the complex assignment operators in Java.

[<>]=?|!=

All the comparison operators in J ava.

[1-9][0-9]*

All decimal integer numerals in Java.

[a-zA-Z_][a-zA-Z0-9_]*

All identiﬁers in C (a letter or und erscore followed by zero or

more letters, digits, and underscores).

//.* //-style comments in C++ and Java.

2.4 Standard Extensions to Regular Expressions

These days, most programming languages prov ide some kind of regular-expression

matching facilities, sometimes built into the language (as in Perl), and sometimes

as part of their standard library (as in Java, C, or Python). Most extend the

simple expressions from §2.3 with additional ones for convenience. The following

are typical. Here, R and R

represent regular (sub)expressions. We use Python

syntax.

20 CHAPTER 2. LEXICAL ANALYSIS

Expression

Description

R{m} Short for R · · · R

| {z }

m times

R{m, n}

R{, n}

Short f or R · · · R

| {z }

m times

R? · · · R?

| {z }

n − m times

; that is, m to n occurrences

of R. By default, m = 0.

R{m, } Short for R{m}R∗; that is at least m occurrences of R.

\d Any single digit.

Any single whitespace character.

Any single non-whitespace character.

^ Matches the emp ty string, but only at the beginning of a

string or (if the right option is set) at the beginning of a line.

This is most useful in cases where one is searching through

a larger string for a substrin g that matches one’s regular ex-

pression.

Matches the empty string, but only at th e end of a string or

(if the right option is set) at the end of a line.

\k Where k > 1 is a single digit, matches the same string that

was most recently matched by the k

parenthesized ex-

pression in this regular expression (the one started by the

left parenthesis counting from the left). For example

‘([a-z]+),\1’ matches “foo,foo” and “bar,bar”, but not

“foo,bar”.

One useful feature of most of these regular-expression matching facilities is the

ability to retrieve the string matched by some portion of the pattern—typically, by

a parenthesized subexpression. Thus , in Pyth on , one can write things like this:

M = re.match(r’Name:\s*(\S+),\s*(\S+)\s*(.*)’, line)

# The r’...’ notation is a "raw string", in which back slashes and the

# characters they preceded are left unchanged.

# M is a "match object", or null (None) if line does not match.

if M:

print "Last name:", M.group(1)

print "First name:", M.group(2)

if M.group(3): # An empty string means "false"

print "Middle name(s):", M.group(3)

This ability to capture pieces of the match requires some additional description

of what an expression matches. For example, so far as the basic deﬁnitions in §2.3

are concerned, the regular expression “((\d+,)*)(\d+,?)(.*)” simply match es

the string “123,456”. But this doesn’t tell us what part of the string the ﬁrst

parenthesized expression matched (.group(1) in Python notation). Any of the

following breakdowns might seem to be correct:

group(1)

group(3) group(4)

"123," "456" ""

"123," "4" "56"

"" "123," "456"

"1" "23,456"

剩余101页未读，继续阅读

CherryWang1997

粉丝: 0
资源: 5

伯克利大学CS164编译原理讲义解析

cs61a-fall:伯克利大学CS语言课程

Algovision:CS164的最终项目

cs231n斯坦福计算机课程课件pdf

ubc dsci 100

ubc eli考试 试题

Uab*Ia-Ubc*Ib

\ube44\ubc00\ubc88\ud638\uac00 \ub9de\uc9c0 \uc54a\uc2b5\ub2c8\ub2e4

三相桥式电压型逆变电路

ubuntu flann

cmake配置pcl1.11.1

最新资源

ubc eli考试试题

UabIa-UbcIb