精华内容
下载资源
问答
  • 编译原理 —— 语言定义

    千次阅读 2019-01-26 17:44:37
    语言的形式化定义 推导 用产生式的右部替换产生式的左部(生成语言) 规约 用产生式的左部替换产生式的右式(识别语言) 判定 有了文法(语言规范),如何判定某一词串是否是满足文法的句子? 从生成语言的...

    语言的形式化定义


    文法和语言之间的联系

    给定一个文法,就能从结构上唯一地确定其语言,即 G → L(G)

    给定一种语言,能确定其文法,但这种文法不是唯一的,即 LG1L → G_1G2G_2 或…或 GnG_n


    句子和句型

    举例:


    推导和规约

    推导:用产生式的右部替换产生式的左部 (生成语言)

    规约:用产生式的左部替换产生式的右式 (识别语言)

    举例:根据下列文法,对 little boy eats apple 进行推导和规约

    有了文法(语言规范),如何判定某一词串是否是满足文法的句子?

    • 从生成语言的角度,如果从文法的开始符号可以推导出词串,则该词串是语言的句子

    • 从识别语言的角度,如果词串可以规约出文法的开始符号,则该词串是语言的句子


    参考地址:

    https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce

    展开全文
  • 语言定义——编译原理

    千次阅读 2020-08-17 09:18:38
    什么是编译原理中的推导和规约,句型和句子,语言的形式化定义

    语言的定义——编译原理

    给定文法G=(VT,VN,P,S),如果α→β∈P,那么可以将符号串中的γαδ中的α替换为β,记作 γαδ⇒γβδ,此时称γαδ直接推导出γβδ.

    推导(derivation)和规约(reduction)

    在这里插入图片描述

    有上述例子可知,推导是一个自顶向下的过程,而规约是自定向上的过程,换句话说:推导是由抽象到具体,而规约是由具体到抽象

    句型和句子

    在这里插入图片描述

    在这里插入图片描述

    语言的形式化定义

    由文法G的开始符号S所推导出来的所有句子的集合称为文法G的生成的语言,记做

    称为文法G的生成的语言,记做

    在这里插入图片描述

    展开全文
  • 下面是关于推导的定义: 当n=1时,即符号串a0经过1步推导出an,记为直接推导。 如下,推导的过程就是用产生式的右部替换左部 相反,规约的过程就是用产生式的左部替换右部 由此得出:推导和规约两者互为逆过程 ...

    推导和规约

    在这里插入图片描述
    下面是关于推导的定义:
    当n=1时,即符号串a0经过1步推导出an,记为直接推导。
    在这里插入图片描述
    如下,推导的过程就是用产生式的右部替换左部
    相反,规约的过程就是用产生式的左部替换右部
    由此得出:推导和规约两者互为逆过程
    在这里插入图片描述


    问题: 有了文法,如何判断某一词串是否是该语言的句子?

    解决办法1:
    由开始符S进行推导,若能推导出该词串,则该词串是该语言的句子。
    解决办法2:
    由该词串进行规约,若能规约到开始符S,则该词串是该语言的句子。


    句子和句型

    S经过正数步推导得出的α是G的一个句型
    在这里插入图片描述
    在刚才的例子中,所有步骤都可以称之为句型,但只有最后一步推导式可以称为句子(因为没有非终结符)。
    在这里插入图片描述
    在这里插入图片描述
    下图中对左边的文法进行分析,由简单的开始:
    D是表示数字串,L表示字母串
    T既可以是数字串,也可以是字母串,同时按照右式可以推导出T可以表示字母数字串
    S推导出的就是字母串或字母数字串,即标识符。

    在这里插入图片描述
    在这里插入图片描述


    短语,直接短语和句柄

    在这里插入图片描述
    在这里插入图片描述


    素短语

    定义: 是指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语
    特殊的:
    最左素短语
    定义: 最左素短语就是句型最左边的素短语,是算符优先分析法的规约对象。
    语法树: 通过语法树分析时,要注意先判断是否为素短语,再找相对最左端的素短语。

    展开全文
  • 编译原理 语言和文法

    千次阅读 2020-09-22 19:50:06
    文章目录语言形式语言符号和符号串文法 语言 语言是其句子的集合。 汉语–所有符合汉语语法的句子的全体 英语–所有符合英语语法的句子的全体 程序设计语言–所有该语言的程序的全体 研究语言={每个句子构成的规律...

    一、语言

    语言是其句子的集合。

    • 汉语–所有符合汉语语法的句子的全体
    • 英语–所有符合英语语法的句子的全体
    • 程序设计语言–所有该语言的程序的全体

    ={使 研究语言=\left\{ \begin{aligned} 每个句子构成的规律 \\ 每个句子的含义\\ 每个句子和使用者的关系 \\ \end{aligned} \right.

    三个方面:

    • 语法 Syntax
      表示构成语言句子的各个记号之间的组合规律
    • 语义 Semantics
      表示各个记号及其组合的特定含义(各个记号和记号所表示对象之间的关系)
    • 语用 Pragmatics
      表示在各个记号所出现的行为中,它们的来源、使用和影响

    1、形式语言

    可用于形式化地描述程序设计语言,包括它由哪些符号串构成,这些符号串的表示、结构和特性

    2、符号和符号串

    任何一种语言都是由该语言的基本符号组成的符号串集合

    一些基本概念:

    • 符号:
      一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。
    • 字母表:
      字母表是元素的非空有穷集合,我们把字母表中的元素称为符号,因此字母表也称为符号集。不同的语言可以有不同的字母表,例如:汉语的字母表中包括汉字、数字及标点符号等,PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。
    • 符号串:
      • 由字母表中的符号组成的任何有穷序列称为符号串,例如00 11 10 是字母表 ∑ ={0,1}上的符号串。
      • 字母表A={a,b,c}上的一些符号串有:a,b,c,ab,aaca。在符号串中,符号的顺序是很重要的,符号串ab就 不同于ba,abca和aabc也不同。
      • 可以使用字母表示符号串,如x=STR表示 x 是由符号S、T和R,并按此顺序组成的符号串。
    • 符号串的长度:
      如果某符号串x中有m个符号,则称其长度为m,表示为|x|=m,如001110的长度是6。
    • 空符号串:
      即不包含任何符号的符号串,用ε表示,其长度为0,即|ε|=0。
    • 符号串的头、尾,固有头和固有尾:
      • 如果z=xy是一符号串,那么x是z的头,y是z的尾;
      • 如果x是非空的,那么y是固有尾;
      • 如果y非空,那么x是固有头。

    例如:设z=abc,那么z的头是ε,a,ab,abc,除abc外, 其它都是固有头;z的尾是ε,c,bc,abc,z的固有尾是
    ε,c,bc。

    当对符号串z=xy的头感兴趣而对其余部分不感兴趣时,采用省略写法:z=x…;
    如果只是为了强调x在符号串z中的某处出现,则可表示为:z=…x…;符号t是符号串z的第一个符号,则表示为z=t…。

    • 符号串的连接:
      设x和y是符号串,它们的连接xy 是把y的符号写在x的符号之后得到的符号串. 由于ε的含义,显然有ε x=x,x ε =x
      例如:x=ST,y=abu,则它们的连接xy=STabu,看出
      |x|=2,|y|=3,|xy|=5

    • 符号串的方幂:
      符号串自身连接n次得到的符号串,an 定义为 aa…aa n个a,a1=a, a2=aa且a0=ε

      • 例:若x=AB,则:
        x0 = ε
        x1 =AB
        x2 = ABAB
        x3 = ABABAB
        xn = xxn-1 = xn-1 x (n>0)
    • 符号串集合:
      若集合A中所有元素都是某字母表 ∑ 上的符号串,则称A为字母表上的符号串集合。

    • 两个符号串集合A和B的乘积:
      定义为 AB = {xy|x∈A且y∈B}
      若集合A={ab,cde} 集合B = {0,1},则
      AB ={ab1,ab0,cde0,cde1}

    使用 ∑* 表示 ∑ 上的一切符号串(包括 ε )组成的集合。Σ* 称为 Σ 的闭包。

    ∑ 上的除ε外的所有符号串组成的集合记为∑+。 ∑+称为Σ的正闭包。

    编译原理的闭包

    V是一个符号集合,假设V指的是三个符号a, b, c的集合,记为 V = {a, b, c } V*
    读作“V的闭包”,它的数学定义是V自身的任意多次自身连接(乘法)运算的积,也是一个集合。
    也就是说,用V中的任意符号进行任意多次(包括0次)连接,得到的符号串,都是V*这个集合中的元素。 0次连接的结果是不含任何符号的空串,记为
    ε 1次连接就是只有一个符号的符号串,比如,a,b, c 2次连接是两个符号构成的符号串,比如,aa, ab, ac, ba, bb,
    bc,等等

    二、文法

    符号>->符号串>->句子>->语言

    并非所有符号串都能形成句子

    文法G定义为一个四元组(VNVTPS)(V_N,V_T,P,S ),其中:

    • VNV_N为非终结符号(或语法实体,或变量)集;

      非终结符(nonterminal) 是用来表示语法成分的符号,有时也称为语法变量

      : VN={<>,<>,<>,<>,}V_N = \{ <句子>, <名词短语>, <动词短语>,<名词>, … \}

    • VTV_T为终结符号集;

      终结符(terminal symbol)是文法所定义的语言的基本符号,有时也称为tokentoken

      例: VT={apple,boy,eat,little}V_T=\{ apple, boy, eat, little\}

    • PP为产生式(也称规则)的集合; VNV_NVTV_TPP是非空有穷集;

      产生式(production)描述了将终结符和非终结符组合成串的方法产生式的一般形式:

      α→β 读作:α定义为β

      • α(VTVN)+α∈(V_T∪V_N)^+,且α中至少包含VNV_N中的一个元素:称为产生式的头(head)或左部(left side)

      • β(VTVN)β∈(V_T∪V_N)^*:称为产生式的体(body)或右部(right side)

        例:

        P={<><><><><><> P=\left\{ \begin{aligned} <句子>\rightarrow<名词短语>\rightarrow<动词短>, \\ <名词短语>\rightarrow<形容词>\rightarrow<名词短语>, \\ …\end{aligned} \right.

    • SS为识别符号或开始符号,它是一个非终结符。

      SVNS∈V_N。开始符号(start symbol ) 表示的是该文法中最大的语法成分

      例:S=<>S = <句子>

    VNV_NVTV_T不含公共的元素,即VNV_NVTV_T = φφ

    VV表示VNV_NVTV_T ,称为文法GG的字母表或字汇表规则,也称重写规则、产生式或生成式,
    是形如α→β或α∷=β的(αβ)(α,β)有序对,其中 α 是字母表VV的正闭包V+V^+中的一个符号,β 是VV^*中的一个符号。
    α 称为规则的左部,β称作规则的右部。

    1、推导

    直接推导:“=>=>

    α→β 是文法G的产生式,若有 δ1, δ2 满足:δ1 =γ1αγ2, δ2 = γ1βγ2, 其中γ1,γ2∈V

    ​ - 则称δ1直接推导到δ2,记作δ1=>=>δ2

    ​ - 也称δ2直接归约到δ1

    例:

    G:S→0S1, S→01

    • 0S1 => 00S11

    • 00S11 => 000S111

    • 000S111 => 00001111

    • S => 0S1

    规范推导:最右推导

    中间为规范推导

    句型、句子的定义

    • 句型
      有文法G,若S =>* x,则称x是文法G的句型。

    • 句子
      有文法G,若S =>*x,且x∈VT{V_T}*,则称x是文法G的句子。

    例:

    G: S→0S1, S→01

    • S =>=> 0S1 =>=> 00S11=>=> 000S111 =>=> 00001111
    • G的句型S, 0S1, 00S11,000S111, 00001111
    • G的句子00001111, 01

    2、语言的定义

    由文法G生成的语言记为L(G),它是文法G的一切句子的集合:

    L(G)={xS=>xSxV}L(G)=\{x|S =>^*x,其中S为文法的开始符号,且x ∈V*\}

    例:G: S→0S1, S→01

    L(G)={0n1nn1}L(G)=\{0^n1^n|n≥1\}

    3、文法等价

    L(G1)=L(G2)L(G1)=L(G2), 则称文法G1G1G2G2是等价的。

    如文法 G1[A]A0RG1[A]:A→0RG2[S]S0S1G2[S]:S→0S1 等价
    A→01 S→01 R→A1

    4、语法树

    文法G[Z]的语法树:

    • 每个结点都是G的符号

    • 树根是文法的开始符号

    • 若某个结点至少有一个从它出来的分支,则该结点一定是非终结符

    • 若某个结点A有n个分支,假设其分支结点为B1,B2,…Bn,则A::=B1B2B3…Bn一定是文法的一条规则

    语法树可以从推导过程产生。

    凡使用一条规则推导,则可以从规则左部符号结点长出若干分支。

    5、句型分析

    句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。

    在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序,分析算法又称识别算法。

    从左到右的分析算法,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号,直到分析结束。

    句型分析分析算法可分为:

    • 自上而下分析法:
      从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导。
    • 自下而上分析法:
      从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。

    两种方法反映了两种语法树的构造过程:

    • 自上而下方法是从文法符号开始,将它做为语法树的根,向下逐步建立语法树,使语法树的结果正好是输入符号串

    • 自下而上方法则是从输入符号串开始,以它做为语法树的结果,自底向上地构造语法树

    句型分析的有关问题

    • 1)在自上而下的分析方法中如何选择使用哪个产生式进行推导?
      假定要被代换的最左非终结符号是A,且有n条规则:A→B1|B2|…|Bn,那么如何确定用哪个右部去替代A?
    • 2)在自下而上的分析方法中如何识别可归约的串?
      在分析程序工作的每一步,都是从当前串中选择一个子串,将它归约到某个非终结符号,该子串称为“可归约串”

    刻画“可归约串”

    • 短语是句型中某非终结符号通过若干步推导出的子串

    • 归约:如果每次都从当前句型的句柄进行归约,则可以归约到文法的开始符号

    6、文法二义性

    • 文法二义性:两棵语法树对应同一句子

    • 根据语法树,可以发现文法的二义性二义文法

    若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的或者,若一个文法存在某个句子有两个不同的最左(右)推导,则称这个文法是二义的。

    判定任给的一个上下文无关文法是否二义,或它是否产生一个先天二义的上下文无关语言,
    这两个问题是递归不可解的,但可以为无二义性寻找一组充分条件。

    文法的二义性和语言的二义性是两个不同的概念
    可能有两个不同的文法G和G′,其中G是二义的,但是却有:L(G)=L(G′),
    即,这两个文法所产生的语言是相同的。

    7、文法分类

    通过对产生式施加不同的限制,Chomsky将文法分为四种类型:

    • 0型文法:对任一产生式 αβα→β,都有α(VNVT)+α∈(V_N∪V_T)^+β(VNVT)β∈(V_N∪V_T)^*
    • 1型文法:对任一产生式αβα→β,都有βα|β|≥|α| ,仅 SεS→ε 除外, S为文法初始符号且不出现在任何产生式右边
    • 2型文法:对任一产生式αβα→β,都有αVNα∈V_Nβ(VNVT)β∈(V_N∪V_T)^*
    • 3型文法:任一产生式αβα→β的形式都为AaBA→aBAaA→a, 其中AVNA∈V_NBVNB∈V_NaVTa∈V_T
    类型 例子
    1型文法
    2型文法
    3型文法

    文法的实用限制:

    ε 规则:

    关于区分上下文是否相关,引入知乎大佬的解释:

    展开全文
  • 编译原理(五) 语言定义

    千次阅读 2020-03-23 10:48:53
    自然语言的文法 <句子> -> <名词短语 > <动词短语> <名词短语> -> <形容词> <名词短语> <名词短语> -> <名词> <动词短语> -> <动词> <...
  • 编译原理 —— 文法的定义

    千次阅读 2019-01-26 17:36:42
    VTV_TVT​:终结符是文法所定义语言的基本符号,有时也称为token。(对应词义分析) VNV_NVN​:非终结符是用来表示语法成分的符号,有时也称为&amp;amp;amp;amp;quot;语法变量&amp;amp;amp;amp;quot;,...
  • 编译原理.第二章.高级程序设计语言概论.程序设计语言定义0 目录2 高级程序设计语言概论2.1 程序设计语言定义2.1.1课堂重点2.1.2测试与作业3 下一章 0 目录 2 高级程序设计语言概论 2.1 程序设计语言定义 2.1.1...
  • 编译原理--正则定义

    2019-01-27 16:12:05
    正则定义是具有如下形式的定义序列: d1→r1 d_1 \rightarrow{r_1} d1​→r1​ d2→r2 d_2 \rightarrow{r_2} d2​→r2​ ... ... ... dn→rn d_n \rightarrow{r_n} dn​→rn​ 其中: 每个did_idi​都是一个新符号...
  • 编译原理编译原理简单介绍

    万次阅读 多人点赞 2017-05-07 13:27:20
    编译原理简单介绍编译原理简单介绍 什么叫编译程序 翻译程序 编译程序 翻译和编译的区别 编译的过程 词法分析 语法分析 语义分析和中间代码的产生 优化 目标代码生成 编译程序的结构 编译程序总框 表格与表格的管理 ...
  • 编译器与解释器 1.定义 编译器:一段将源程序转化为...对于编译语言分为两步:1. 源程序——编译器——目标程序 2. 输入——目标程序——输出 对于解释性语言只需要一步:源程序+输入——解释器——输出 2....
  • 0型语言PSL也叫短语结构语言或递归可枚举集。 1型文法也叫上下文有关文法,CSG。1型语言CSL也叫上下文有关语言。 2型文法也叫上下文无关文法,CFG。2型语言CFL也叫上下文无关语言。 3型文法也叫正则文法或正规...
  • 编译原理---文法和语言

    千次阅读 2017-10-14 10:34:02
    编译原理文法和语言类型
  • 编译原理-文法的定义与分类

    千次阅读 2020-12-21 19:45:21
    编译原理-文法的定义与分类前言一、文法的定义二、文法的分类0.短语结构语言(PSL)1.上下文有关文法(CSG)2.上下文无关文法(CFG)3.正规文法(RG)三、判断以下文法的类别 前言 语言是一定的群体用来信息交流的工具 ,而...
  • 编译程序要对程序进行正确的翻译,首先要对程序设计语言本身进行精确地定义和描述。对语言的描述是从三个方面来考虑(精简地说): 语法:是对语言结构的定义(什么样的符号序列是合法的);定义语言的词法和语法的...
  • 编译原理

    千次阅读 2014-09-11 23:00:28
    编译过程就是把预处理的文件进行一系列此法分析,语法分析,语义分析以及优化后生产相应的汇编代码文件。主要分为5部分,分别是:词法分析、语法分析、语义分析、中间语言生产和...本文图示介绍编译原理的整个过程。
  • 由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)={x|S x,其中S为文法的开始符号,且x ∈VT*} 例:G: S→0S1, S→01 L(G)={0n1n|n≥1}
  • 本文以课堂内容为主方法1:逐步求精法自上而下L1={aibjck|i,j,k≥1}L1 = \{a^ib^jc^k|i, j, k ≥ 1\}记ai=Aa^i = Abj=Bb^j= Bck=Cc^k = Cai=a∗ai−1=a∗ama^i = a*a^{i-1}=a*a^mA→aAA\to aAA→aA\to a∴A→aA|a\...
  • 编译原理系列】文法的定义

    千次阅读 2016-12-26 09:06:26
    当我们要描述一种语言时,需要给出这种语言的所有句子,当句子的数目是有限可数时,就要都列出来;当句子是一个无穷集,也就是无限不可数时,就要给出可以表示它们的结构的描述方法或者说,句子的组成规则。这种规则...
  • 参考:《程序设计语言——编译原理》第3版 陈火旺 刘春林 谭庆平 赵克佳 刘越 编著 国防工业出版社 程序设计语言——编译原理(二、高级语言及其语法描述) 高级程序语言是用来描述算法和计算机实现这双重目的...
  • 编译原理 —— 正规式、正规集和正则定义

    万次阅读 多人点赞 2019-01-26 18:03:53
    正则表达式的定义 ...每个正则表达式r定义(表示)一个语言,记为L(r)。 ε是一个RE,L(ε)={ε} 如果a是任意一个符号,则a是一个RE,L(a)={a} 引用图片的语法: 运算的优先级:*、连接、| 示例 ...
  • 编译原理Pl/0语言 简单编译器思路

    千次阅读 2016-12-21 16:46:27
    基于山东大学编译原理实习题,实现的简单的编译器。对编译过程代码的解读,相关代码请联系作者
  • 在我刚刚进入大学,从零开始学习 C 语言的时候,我就不断的从学长的口中听到一个又一个语言,比如 C++、Java、Python、JavaScript 这些大众的,也有 Lisp、Perl、Ruby 这些相对小众的。一般来说,当程序员讨论一门...
  • 编译原理(2):文法和语言

    千次阅读 2017-09-17 19:35:30
    介绍文法和语言定义,字母表(符号集)和字符串上的操作,文法的类型,上下文无关文法及其语法树,提供典型例题和详细解答。
  • 0型文法产生的语言称为0型语言。 1型文法产生的语言称为1型语言,也称作上下文有关语言。...文法分类(A hierarchy of Grammars)著名语言学家Noam Chomsky定义了四类文法和四种形式语言类,文法的四种类型分别是0
  • 编译原理--文法和语言

    千次阅读 2017-09-27 19:35:54
    1、左递归的定义: 对于某些α,存在推导 A =+> A α 这样妨碍自顶向下方法的使用。 2、消除直接左递归的方法 (1)直接删除左递归的产生式(老师上课没讲,我也不清楚是怎么回事orz) (2)引入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 155,795
精华内容 62,318
关键字:

编译原理语言定义