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.正規(guī)式是用于說明詞法單元如何到對應(yīng)到詞法記號的模式。與非形式化的描述相比，正規(guī)式更具形式化，更加精確。

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(chǎn)’(a|b)* allthestringsconsistingof‘a(chǎn)’and‘b’2.2.3NamesofREForbrevity,wecannamesomeREs。d1

r1d2

r2...dn

rndimustbedifferentfromeachotherEveryrimustbeaFEover{d1,d2,…,di-1}這樣就保證了，每個名字對應(yīng)的正規(guī)式中使用的各種符號已經(jīng)在前面定義了，從而可以避免遞歸定義的情況。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|