补充资料：文法

文法
grammar

　　WenfQ文法(语言结构的一种有限描述。给定任意的有限字母表乞，艺“表示由乞中的字母组成的所有符号串(包括空串)的集合。乞‘的每个子集都是乏上的一个语言。形式语言主要研究这种界限明确的语言。N.口1《】1巧ky于1959年提出的生成文法是形式语言的一种描述手段。形式上，生成文法是一个四元组 G=(乞，V，S，尸)其中V是有限的变量集合，又称为非终结符号表;乞是有限的字母集合，又称为终结符号表，V门忍=曰;S是开始符号，S〔V;尸是有限的形如。~召的生成式集合，a〔(vU乏)’V(VU乏)‘，召任(vU乏)‘。生成式又称为规则。在不对文法G的生成式增加限制时，称文法G为无限制文法，或者短语结构文法，或者O型文法。 推导由文法生成语言的句型的过程。给定文法G=(艺，V，S，p)和。’，召’e(vU乏)‘，如果a’=夕‘或者存在al，。2，。，召任(VU艺)’，使得。‘=。laaZ，召’=。1月。:且(。~召)任p，则称在文法G中“‘直接推导为洲，记为“‘护。用=>表示冷的自反传递闭包。如果S二、，a〔(VU艺)’，则称a G为文法G生成的句型。文法G生成的所有的句型的集合S(G)={a〔(VU艺)“lS秒例如短语结构文法Gl=(la，西}，{S，A，B，C}，S，pl)，其中尸1二{S~ASa，S~刀品，S~C，AC~aC，仪了~瑟，A“~亿A，Ba~aB，A乙~bA，份~bB，C~人}，则有推导 S=>A肠=>八BS反2=> Al义{轰之=> Ab(入之冷乙A(人刁 GIG一GI GI Gr今撇〔加二》加兔Gl GI这里S，A反，八B及地，Aa口如，A厌加，bA〔人之，撇。‘和加加都是Gl生成的句型。 短语结构语言短语结构文法生成的所有句子的集合。如果文法G=(乞，V，S，P)，a任S(G)且a任艺签，则a是文法G生成的句子。文法G生成的语言 L(G)=S(G)门艺’二{二〔乏“15宾板更} G0型文法生成的语言称为O型语言或者短语结构语言。例如在上面给出的文法Gl中，“育加撇，故加撇任乞’是L(G，)的一个句子。实际上，文法GI生成的短语结构语言毛(GI)=}uu}u任}a，占}’}。
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。