词汇分析限制1re limits重新.pdfVIP

ChomskyHierarchy

RELimitations1

•REscandescribeonlyregularlanguages

•REfiniteautomaton,whichhasafinitenumberof

states(andtheirtransitions),andnothingelse

–Hence,can’thandle(i.e.,can’twriteaREfor)stringsneedingan

unlimited#states

nn

•E.g.,{ab|n0}–needstatestocount,andncanbeinfinite

•Generalizestonestedparentheses(a=“(“,b=“)”),nestedcomments…

–Whataboutthefollowing?

nn-1-1

•{aba}–thisisa“palindrome”,or{ss}or{sas},wheresisa

stringands-1issreversedThemachineneedsmorethan

counting(aqueue?)

•{an}

•{anbn|n55}Findtheminthispage!

2

RELimitations2

•Thepumpinglemmaisoftenusedtoformallyprovethata

languageisnon-regular

•Nestedstructures(parentheses,comments,etc.)needa

stackofsufficientlylargesizefortheirprocessing

–Whenseeing“(“,push;whenseeing“)”,pop

–N/DFA(forlexers)donothavestacks

•Ofcourseyoucanaddyourownstackinyourlexer(theresultisnotapure

DFA!)

–Parsershavestacks

•flex/lexprovides“startstates”(or“startconditions”)

–TheyallowthelexertochooseamongtheavailableREsin

differentsituations

–=scoping

3

Statesinflex/lex1

•Problem:TwocommonmodesofRE

–Writealexertocapitalizethefirst