语法生成规则如何与ECMAScript中的解析相关



正如维基百科关于解析的文章中所指出的,这个过程有三个阶段:

  1. 词法分析(标记化):将Unicode代码点转换为标记
  2. 语法分析:验证令牌流是否形成有效的脚本/模块,并创建解析树
  3. 语义分析:令牌的额外验证(在创建解析树之后发生?)

除了上面阶段(3)中的小混乱之外,我想验证我对ECMAScript过程的理解是否正确。

因此,以下流程是否正确?


词汇分析阶段(ECMAScript第11条)

  • 输入:Unicode代码点流<--词汇语法中的终端符号
  • 输出:有效令牌<--词汇语法中的非终端符号
  • 语法的应用
    1. 分析每个Unicode码点(字符),每次一个
    2. 通过应用适当的产生式规则,将终端符号的最长序列替换为非终端符号
    3. 然后,通过应用产生式规则,替换尽可能长的非终结符序列
    4. 以同样的方式,生产规则被一次又一次地应用,一直到产生"目标符号">
  • 目标符号是语法分析阶段(下一阶段)的输入元素(也称为标记)
  • ECMAScript的词法语法存在多个"目标符号"(规范说明要选择哪个)

句法分析阶段(ECMAScript第12-15条)

  • 输入:令牌流<--句法语法中的终端符号
  • 输出:解析树,以Script | Module作为根解析节点<--句法语法中的非终端符号
  • 语法的应用
    1. 从输入元素流开始。代币
    2. 这些标记是句法语法中的终端符号
    3. 通过将最大符号流与适当生成规则的RHS匹配,然后用该规则的LHS非终结符替换流,应用生成规则
    4. 这种情况一直持续到只剩下"进球符号">
  • ECMAScript:如果我们可以替换所有的终端符号(令牌),以单个"目标符号"结束,则程序是有效的(Script|Module)

语法解析不遵循"最大咀嚼量";规则(选择最长的匹配前缀)。事实上,据我所知,ECMA-262没有指定解析算法,但提供了一个明确的上下文无关语法,可以进行解析,例如使用自下而上(LR(k))语法分析器,除了处理自动分号插入的一些问题和对跨换行符(这不是语法标记)的生成的一些限制之外。

然而,如§5.1.4所述,语法实际上承认语言的超集;以补充语法的形式提供了额外的限制。

有一点需要澄清:拥有多个上下文相关的词汇目标符号的复杂性使得首先将输入划分为词元,然后再将词元组合成解析树变得困难。如果没有至少一个部分解析,就不可能知道每个点的正确词汇目标符号,因此将句法和词汇解析交错是很方便的。实际的语法分析算法是从左到右操作的,基本上按照输入顺序处理词法,因此可以根据需要进行词法分析,只有在语法分析器需要更多输入才能继续时才能找到词法。

但除此之外,你概述的整体结构是正确的。在词法解析中,将词尾(字符)的最长可能前缀聚合为非词尾,以创建词法位(根据需要哪个词法目标的稍微复杂的规则);在句法分析中,词尾(lexeme)被聚合成非词尾,以产生对应于两个句法目标符号之一的单个解析树。

正如现实世界中的语言经常发生的情况一样,现实并没有那么干净。除了需要解析器指示需要哪个词法目标之外,还有换行规则和自动分号插入,这两种规则都跨越了词法和句法解析之间的界限。


注意:

";终端";以及";非终端";这可能有点令人困惑,但我(和ECMA标准)在无上下文语法中使用它们的标准含义。

上下文无关语法由生成组成,每个生成具有以下形式:

N ⇒ S …

其中CCD_ 2是非终端符号,并且CCD_。终端符号是要识别的字符串表示中的原子。

标准解析模型将解析分为两个层次:词法和句法。原始输入是一个字符序列;词汇分析将其转化为一系列词汇,这些词汇是句法分析的输入。

一个标准的上下文无关语法有一个单目标符号,它是语法定义的非终端之一。如果整个输入可以减少到这个非终端,则解析成功。

词汇扫描可以被视为一种上下文无关的语法,具有有序的目标符号列表。它依次在输入的较长前缀上尝试每个目标符号,并接受与最长前缀匹配的第一个目标符号。(在实践中,这一切都是并行的;我在这里谈论的是概念性的。)当ECMA-262谈论不同的词汇目标时,它实际上意味着可能的目标非终端的不同列表。

用语义属性扩充符号也很有用;这些属性不会影响解析,但一旦解析完成,它们就会很有用。特别地,解析树是通过将树节点作为属性附加到解析过程中从产品创建的每个非终端来构建的,因此解析的最终结果不是非终端符号本身(在解析开始之前就已经知道了),而是附加到非终端的特定实例的语义属性,而在每个点的词汇扫描的结果是非终端符号及其相关联的语义属性;通常,语义属性将是相关联的输入序列,或者这些字符的某些功能。

在任何情况下,两级解析都涉及将词法级别的输出非终端作为句法级别的终端。

最新更新