计算理论导论(英文版)上下文无关语言ppt课件.ppt

《计算理论导论(英文版)上下文无关语言ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter2Context-FreeLanguages(CFL)1DescribinglanguageFiniteautomataRugularexpressionNonrugularexpressionContext-freegrammarCandescribecertainfeaturesthathavearecursivestructurewhichmakesthemusefulinavarietyofapplications.Thetaskofprogrammingisinmanycaseseasierwhenrecursionisallowed.2Context-freegram

2、marWerefirstusedinthestudyofhumanlanguages-thereexistsanaturalrecursionUsedinthespecificationandcompilationofprogramminglanguagesgrammar–thelanguagesyntaxDesignersofcompilersandinterpretersforprogramminglanguages-agrammarforthelanguage.compilersandinterpreters－parserToconstructaparser–acontext-freeg

3、rammarisavailableSometools:YACC(YetAnotherCompiler-Compiler)34Context-FreeGrammarsWhichsimplemachineproducesthenonregularthelanguageof{0n1n

4、nN}?StartsymbolSwithrewriterules:1)S0S1//Symmetricgenerationof0and1onbothsidesofS2)SSyields0n1naccordingtoS0S100S11…0nS1n0n1n5Context-freegrammarsallo

5、wustodescribenonregularlanguageslike{0n1n

6、n0}Algol,Pascal,C,…,etcareallCFLsNaturallanguageisnotCFLGeneralidea:CFLsarelanguagesthatcanberecognizedbyautomatathathaveonesinglestack:Automata+AStack{0n1n

7、n0}isaCFL{0n1n0n

8、n0}isnotaCFL(Onestackisnotenoughandmoreresourcesarenecessary)6Context-FreeGramm

9、arsAcontextfreegrammarisa4-tuple(V,,R,S),whereV:afinitesetvariables:finitesetterminals(withV=)R:finitesetofsubstitutionrulesorproductionrulesV(V)*//Onevariableonleftside,anysymbolsonrightsideS:startsymbolVThelanguageofgrammarGisdenotedbyL(G):L(G)={w*

10、Sw}L(G)istheso-calledCFL.*7Derivation

11、Asinglestepderivation“”consistofthesubstitutionofavariablebyastringaccordingtoasubstitutionrule.Example:withtherule“ABB”,wecanhavethederivation“01AB001BBB0”.Asequenceofseveralderivations(ornone)isindicatedby“”Sameexample:“0AA0BBBB”***8RemarksIfSw,wisasentencewhenonlyterminalinclusive;othe

12、rwiseitisasentencepattern.ThelanguageL(G)={w*

13、Sw}containsonlystringsofterminals,novariables.**9ExampleConsidertheCFGG=(V,,R,S)withV={S，Z}={0,1}R:S0S1

14、0Z1//两边长翅膀

15、SZZ0Z

16、//左边长翅膀。右边不长

17、变空字ThenL(