您的位置: 首页  >  文章  >  编译原理-词法分析-上下文无关文法

编译原理-词法分析-上下文无关文法

分类: 文章 • 2023-03-26 00:18:24

通过词法分析, 可以将一个字符串转换成记号流, 但是记号流如何转换成语法树, 需要进行语法分析.

  • 实质: 无结构的数据转化成有结构的数据
  • 依据: 上下文无关语法

上下文无关文法

  • 前言

    • 正规式来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复, 但
    • 正规式不能用于描述配对或嵌套的结构

  • 定义

    • 上下文无关文法是四元组( VT,VN,S,PV_T,V_N,S,P )
      • VTV_T: 终结符集合(非空有限集合)
      • VNV_N: 非终结符集合( VT⋂VN=∅V_T \bigcap V_N = \emptyset )
      • S: 开始符号
      • P: 产生式集合 ( 产生式形式如A→α其中A∈VN,α∈(VT⋃VN)∗A \rightarrow \alpha 其中 A \in V_N, \alpha \in (V_T \bigcup V_N)^* )
    • 例子
      $ ( {id,+, \ast ,-,(,) } , {expr,op} , expr , P ) $
      其中P包括:
      expr →\rightarrow expr op expr
      expr →\rightarrow (expr)
      expr →\rightarrow -expr
      expr →\rightarrow id
      op →\rightarrow +
      op →\rightarrow *

  • 优点

    • 文法给出了精确的，易于理解的语法说明
    • 自动产生高效的分析器
    • 可以给语言定义出层次结构
    • 以文法为基础的语言的实现便于语言的修改

  • 缺点

    • 文法只能描述编程语言的大部分语法

  • 文法推导

    • 推导: 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替
      以文法 $ E \rightarrow E+E|E \ast E|(E)|-E|id$为例:
      存在代换序列: $ E \Rightarrow E+E \Rightarrow id+E \Rightarrow id+id $
      这个代换序列即从E到id+id的推导,
    • 一般而言, 由上下无关文法产生的语言叫上下文无关语言
    • 若两个文法产生相同的语言, 则称这两个文法等价
    • 若存在S⇒∗α\Rightarrow ^\ast \alpha, 若α含非终结符, 则称其为文法的句型, 只含有终结符的句型, 称之为句子
    • 在推导过程中, 每一步都代换句型中最左边的非终结符的推导,称之为最左推导(写作α⇒lmβ\alpha \Rightarrow _{lm}\beta), 类似的,存在最右推导(写作α⇒rmβ\alpha \Rightarrow _{rm}\beta), 最右推导亦称为规范推导

  • 分析树

    • 分析树即推导的图形表示.
    • 例子:
      以文法 $ E \rightarrow E+E|E \ast E|(E)|-E|id$为例:
      编译原理-词法分析-上下文无关文法
      对于同样的句子, 其 最终 分析树是一样的, 但过程会有不同.

  • 二义性

    • 文法的二义性，是指对于符合文法规则的同一个句子，存在两种可能的分析树
    • 考虑如下的情况:
      编译原理-词法分析-上下文无关文法
      对于同一个句子, 该句子存在二义性, 分析树存在了不同, 也带来了不同的释义, 左边的为 id*(id+id), 而右边为 (id*id)+id, 但对于句子id*id+id, 一般认为(id*id)+id是正确的
    • 如何消除二义性, 一般而言, 需要加入消除二义性的规则
    • 以文法 E→E+E∣E∗E∣idE \rightarrow E+E|E \ast E|id为例:
      可以更改为如下规则:
      E→E+T∣TE \rightarrow E + T | T
      E→E∗F∣FE \rightarrow E \ast F | F
      F→id∣(E)F \rightarrow id | (E)

  • 正规式可以描述的语言都可以用上下文无关文法来描述

  • NFA转化为上下文无关文法:

    1. 确定终结符集合
    2. 为每个状态引入一个非终结符AiA_i
    3. 如果状态i有一个转换a到状态j, 则引入产生式Ai→aAiA_i \rightarrow aA_i, 如果i是接收状态, 则引入Ai→ϵA_i \rightarrow \epsilon
      例子:
      编译原理-词法分析-上下文无关文法

  • 为什么要用正规式定义词法

    • 词法规则非常简单,不必用上下文无关文法
    • 对于词法记号,正规式描述简洁且易于理解
    • 从正规式构造出的词法分析器效率高

  • 把词法分析从语法分析中分离出来的理由

    • 简化设计
    • 编译器的效率会改进
    • 编译器的可移植性加强
    • 便于编译器前端的模块划分

  • 能否把词法分析并入到语法分析中,直接从字符流进行语法分析?

    • 若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂
    • 注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多

个人博客:https://qidianxuan.cn/2019/11/25/编译原理-语法分析-上下文无关文法-文法和语言/

相关推荐