编译原理课件lesson

LastLectureRevisitedWhatandWhytostudythiscourse?Def.oftranslatorandcompilerStructureofcompiler,front-end,back-end“Pass”Chapter2.LexicalAnalysis

LexicalAnalyzerSyntaxAnalyzerSymbolTableTokenGetnexttokenSourceCode

词法分析器语法分析器符号表记号取下一个记号源程序Whatlexicalanalysisdoes：LexicalanalyzerTokensSourcecode2.1Tokenandattributes2.1.1Token、pattern、lexeme

Lexeme：stringsinsourcecode。Token：atokenrepresentatypeofstringssubjecttosomerules(patterns)。Pattern:determineshowatokenrelatestolexemesletterssequenceslexemetokenpatternAnexampleeg：var

count

:

integer

;

count

=

5

;lexemeletterssequenceslexemetokenpatternToken

Examples

DescriptionofPatterns

var var varfor for forrelation <,<=,=,… <or<=or=or…id sum,count,D5 letterandnumberstringstartingwithaletternum 3.1,10,2.8E12 anynumericalvalueliteral “seg.error” thestringwithin“”

TokensandpatternsToken

Examples

Patterndescriptionrelation <,<=,=,… <or<=or=or

…id sum,count,D5 letterandnumberstringstartingwithaletternoun

Dalian,Sea

namesofthingsToken

Examples

PatterndescriptionToken

Examples

PatterndescriptionChinese

ZeminJiang male/femalewithChinanationalityAmerican

Clinton,Obama male/femalewithUSAnationality 2.1词法记号及属性SomeissuesinthehistoryShouldweomittheblanksornot?

DO8I3.75 DO8I3.75DO8I3,75Shouldwereservethekeywordsornot?

IFTHENTHENTHEN=ELSE；ELSE…2.1.2Attributesoftokens

position:=initial+rate*60

id，pointertothepositioniteminthesymbletable assign_op，

id，pointertotheinitialiteminthesymbletable add_op，+

id，pointertotherateiteminthesymbletable

mul_op,* num，60

Exerciseofsymboltable：Writeapieceofcodetocalculatethenumberofwords,thenumberofdistinctwords.

eg:IloveDalianandIloveDLUTWordnumber：7Distinctwordnumber：52.1.3LexicalErrorsIt’shardtofindthefollowingerror,sincelexicalanalysisislocallyinsightful.

fi(a==f(x))

…Anexception: 123.2.1.3LexicalErrorsRecovery“emergencymodel”

“recoverytry”deleteanadditionalcharacter

insertamissingcharacter

replaceaninvalidcharacterwithanvalidone

swaptwoadjacentcharacters2.2DescriptionandIdentificationofTokens2.2.1StringandLanguageAlphabettable：setofsymbol，eg.={0,1}String：sequenceofsymbols,eg.0110,Language：setofstrings {,0,00,000,…},{},Sentence：stringinalanguage字母组合串语言集合集合字母表词法单元记号模式emptystring2.2.1StringandLanguageOperatorsoverstringsconcatenation:

xy，s

=s=s

Product（exponent）:

s0=，si=si-1s（i>0）

Operatorsoverlanguagesplus：L∪M={s|s

L或s

M}concatenation：LM={st|s

L且t

M}exponent：L0是{

}，Li是Li-1L

closure：L=L0∪L1∪L2∪…positiveclosure：L+=L1∪L2∪…e.g.2.2（p14）L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L∪D,LD,L6,L*,L(L∪D)*,D+

2.2.2RegularExpression(RE)Regularexpression：Accordingtoasetofrules,formalregulationsshowhowtoformlanguagesfromscratch.正规式是用于说明词法单元如何到对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确。

RE

languagedefined

description

{}

a {a} a (r)|(s)L(r)∪L(s) randsareFEs (r)(s)

L(r)L(s) randsareFEs

(r)*

(L(r))* risaFE

(r) L(r) risaFEPrioritiesofoperators：*>concatenation

>|

SomeexamplesofRE={a,b}a|b

{a,b}(a|b)(a|b)

{aa,ab,ba,bb}aa|ab|ba|bb

{aa,ab,ba,bb}a* allthestrings

consistingof‘a’(a|b)* allthestringsconsistingof‘a’and‘b’2.2.3NamesofREForbrevity,wecannamesomeREs。d1

r1d2

r2...dn

rndimustbedifferentfromeachotherEveryrimustbeaFEover{d1,d2,…,di-1}这样就保证了，每个名字对应的正规式中使用的各种符号已经在前面定义了，从而可以避免递归定义的情况。ExamplesofRE

IDsinPascal letter

A|B|…|Z|a|b|…

|z

digit

0

|1|…|9 id

letter(letter|digit)*

UnsignednumbersinPascal1946,11.28,63.6E8,1.99E6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+||)digits)|

numdigitsoptional_fractionoptional_exponentSimplifiednotations: num

digit+(.digit+)?(E(+|)?digit+)?

Simplifiednotations：r+=rr*r?=r|[a-z]=a|b|c|…|z whilewhile dodo relop<|<=|=|<>|>|>= idletter(letter|