编译原理笔记——文法和语言的基本知识

2020-02-16  本文已影响0人  没昔

学习一门语言最基础的就是语言基础,编译程序要正确准确的翻译程序设计语言,我们从程序设计语言的语法、语义、语用三个因素来考虑。

        语法:对语言结构的定义

        语义:描述语言的含义

        语用:非形式化的描述

非形式化的描述不够准确,为了精确定义程序设计语言采用形式化的方法(形式化的方法是著名语言学家Noam Chomsky用一整套带有严格规定的符号体系来描述问题滴方法)让我们一起来看看编译原理的形式语言理论吧!

§字母表和符号串

  (1) 定义:

    字母表:元素的非空有穷集合  任何语言的字母表指出了该语言允许出现的一切符号

    符号(字符):字母表中的元素

    符号串(字):符号的有穷序列  符号串是字母表里面的符号的有穷多个组合,符号串的符号的顺序很重要

  (2)符号串的运算.

        (a) 符号串的连接:xy是把y的符号写在x的符号之后得到的符号串

                            空串 ε: 不包含任何符号的符号串 ,是符号串不是集合 (注:空串也有连接运算εx = xε =x )

                            ε和 Ø 不同,Ø ={}

                            例:x=abc,y=10a,则xy=abc10a,yx=10aabc

        (b) 符号串的幂运算:把x自身连接n次得到的符号串

                                x^0 =ε,x^1=x,x^2=xx...

                                对于n>0, 有x^n = x·x^{n-1}

                            例:x=abc则,x^0=ε;x^1=abc;x^2=abcabc

        符号串的集合  : 由字母表上的符号串组成的集合 ,现在假设U和 V是符号串集合

          (a) U和V的乘积(连接):满足α∈U且β∈V的所有符号串αβ所构成的集合

                                UV= {αβ|α∈U且β∈V}

                        例:A={a,b},B={c,d},则AB={ac,ad,bc,bd}

          (b)集合的幂运算:

                                  V自身的n次乘积 V^n =VV…V=V`V^{n-1}

                                V^0={ε}

                                例:设A={a,b},A^0 ={ε},A^1={a,b},A^2=AA{aa,ab,ba,bb},A^3 =A^2`A={aaa,aab,aba,abb,baa,bab,bba,bbb}

            集合的正闭包和闭包:(集合A的闭包比正闭包多包含一个空符号串ε)

                              ∑* = ∑0∪∑1∪∑2 … ∪ ∑n ∪ … ={ε}∪ ∑+

                              ∑+ = ∑1 ∪∑2 … ∑n…

                              ∑*  = ∑0 ∪ ∑+

                              ∑+  = ∑*- {ε}

                              ∑+  = ∑∑* = ∑*∑

                              对所有的∑, 有ε∪∑*

§文法和语言的形式定义

        形式语言:序列的集合称为语言,每个形式语言都是字母表上按照某种规则构成的符号串集合

        (1)文法的形式定义

            (a)规则(产生式)

                  A(符号)->B(符号串)  符号生成符号串

                  符号分为终结符号(一般小写)和非终结符号(一般大写)

                终结符号∩非终结符号=Ø,终结符号∪非终结符号=字汇表

              (b)文法

                  文法是规则的有穷集合,通常表示为四元组A=(非终结符号集合,终结符号集合,文法规则集合,文法的开始符号非终结符号至少在一条规则作为左边出现)

                例1:设字母表∑={a,b},L={a^{2n},b^{2n}|n>=1},则语言L是偶数个a偶数个b符号串组成的集合定义L语言的文法为:

                G(V_{N} ,V_{T} ,P,S)

                其中,V_{N} ={A,B,D},V_{T} ={a,b},

                            P={A->aa|aaB|bb|bbD

                                B->aa|aaB

                                D->bb|bbD}

                                S=A

                例2:设计一个表示所有标识符的文法

                        G(V_{N} ,V_{T} ,P,S)

                        其中,V_{N} ={I,L,D}, V_{T} ={a,b,c,...,x,y,z,0,1,2,3,...,9},

                            P={I->L|IL|ID

                                L->a|b|c|...|x|y|

                                D->0|1|2|3|...|9}

                            S=I

              例3:字母表∑={a,b},设计文法描述语言L={ab^na|n>=0}

                第一步:找语言符号串的规律当n=0时L={aa},n=1,L={aba}...得出L={aa,aba,abba,..}

                第二步,定义语言的文法为:G=({A,B},{a,b},{A->aBa,B->Bb|ε},A)

        (2)语言的形式定义

        如何给出已知文法所定义的语言呢?

首先知道以下一点

•直接推导(推导长度=1)

G是一个文法,A->a是G的一个规则,x,y\in V_{N} V_{T} )*,xAy=>xay只使用一次规则推出,则为直接推导。(注:推导是=>而不是规则->)

•推导(推导长度>=1)

      (a)最左直接推导()

            每次换最左边该还的符号,然后换第二次最左边该换的符号,一直换到最后

        (b)最右直接推导

            每次换最右边该还的符号,然后换第二次最右边该换的符号,一直换到最后

•广义推导(推导长度>=0)

            不一定是从开始符合开始推导

•句型和句子

        句型:x\in (V_{N} V_{T} )*

        句子:x\in V_{T} *

•语言

        所有句子的集合称为语言

        例:设有文法G[S]:=S->01|0S1求该文法所定义的语言

              S=>0S1=>00S11=>000S111...=>0(n-1)S1(n-1)=>0n1n

              L(G[S])={0n1n|n>=1}

规范推导也就是最右推导,=>

规范归约也是就是最左归约,是规范推导逆过程推,注意=>•在箭头上有个点

上一篇下一篇

猜你喜欢

热点阅读