编译原理准备

BNF范式 - 巴恩斯范式

BNF范式是一种用递归的思想来表述计算机语言符号集的定义规范
法则:

::= 表示定义；
“”双引号里的内容表示字符；
<>尖括号里的内容表示必选内容；
|竖线两边的是可选内容，相当于or；

BNF规定是推导规则(产生式)的集合，写为:

<符号> ::= <使用符号的表达式>

这里的<符号>是非终结符，而表达式由一个符号序列，或用指示选择的竖杠’|’ 分割的多个符号序列构成，每个符号序列整体都是左端的符号的一种可能的替代。从未在左端出现的符号叫做终结符。

参考

AST

这里直接学习AST概念，不进行深入探讨。后边做编译原理的时候，会有涉及。内容的例子直接挪用参考文章的示例，参考文章使用其他工具部分不是本文涉及。后边会跟进学习cpp 编译原理的前端部分。

AST是什么

Abstract Syntax Tree，它是源代码结构的一种抽象表示。他一树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构

这里贴出参考中好用的转换工具: https://astexplorer.net/

入门AST

可以看到对应的关系:

var 是关键字(keyword)
AST 是最小单元(Identifier)
= 是Equal等号
is tree 是一个字符串
; 是Semicolon

词法分析

词法分析也称之为scanner，对每一行每个char 过滤一遍，分解每个词块。

这块不多介绍，和下面语法分析一起进行。

语法分析

语法分析会将词法分析出来的token转化成有语法含义的抽象语法树结构，并加上类型描述。这步骤验证语法，词法分析仅是读取每个char，根据段落转化一个个token。

开搞例子

以下是直接抄原作者例子, 请直接看原作者链接

例子1

const fn = a => a;

例子2

const fn = a => {
    const i = 1
    return a + 1
}

{
  "type": "Program",
  "start": 0,
  "end": 52,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 52,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 6,
          "end": 52,
          "id": {
            "type": "Identifier",
            "start": 6,
            "end": 8,
            "name": "fn"
          },
          "init": {
            "type": "ArrowFunctionExpression",
            "start": 11,
            "end": 52,
            "id": null,
            "expression": false,
            "generator": false,
            "async": false,
            "params": [
              {
                "type": "Identifier",
                "start": 11,
                "end": 12,
                "name": "a"
              }
            ],
            "body": {
              "type": "BlockStatement",
              "start": 16,
              "end": 52,
              "body": [
                {
                  "type": "VariableDeclaration",
                  "start": 21,
                  "end": 32,
                  "declarations": [
                    {
                      "type": "VariableDeclarator",
                      "start": 27,
                      "end": 32,
                      "id": {
                        "type": "Identifier",
                        "start": 27,
                        "end": 28,
                        "name": "i"
                      },
                      "init": {
                        "type": "Literal",
                        "start": 31,
                        "end": 32,
                        "value": 1,
                        "raw": "1"
                      }
                    }
                  ],
                  "kind": "const"
                },
                {
                  "type": "ReturnStatement",
                  "start": 36,
                  "end": 48,
                  "argument": {
                    "type": "BinaryExpression",
                    "start": 43,
                    "end": 48,
                    "left": {
                      "type": "Identifier",
                      "start": 43,
                      "end": 44,
                      "name": "a"
                    },
                    "operator": "+",
                    "right": {
                      "type": "Literal",
                      "start": 47,
                      "end": 48,
                      "value": 1,
                      "raw": "1"
                    }
                  }
                }
              ]
            }
          }
        }
      ],
      "kind": "const"
    }
  ],
  "sourceType": "module"
}

例子3

    function test() {
  let a = 1
  console.log(a)
}

{
  "type": "Program",
  "start": 0,
  "end": 60,
  "body": [
    {
      "type": "FunctionDeclaration",
      "start": 0,
      "end": 60,
      "id": {
        "type": "Identifier",
        "start": 9,
        "end": 13,
        "name": "test"
      },
      "expression": false,
      "generator": false,
      "async": false,
      "params": [],
      "body": {
        "type": "BlockStatement",
        "start": 16,
        "end": 60,
        "body": [
          {
            "type": "VariableDeclaration",
            "start": 24,
            "end": 33,
            "declarations": [
              {
                "type": "VariableDeclarator",
                "start": 28,
                "end": 33,
                "id": {
                  "type": "Identifier",
                  "start": 28,
                  "end": 29,
                  "name": "a"
                },
                "init": {
                  "type": "Literal",
                  "start": 32,
                  "end": 33,
                  "value": 1,
                  "raw": "1"
                }
              }
            ],
            "kind": "let"
          },
          {
            "type": "ExpressionStatement",
            "start": 40,
            "end": 54,
            "expression": {
              "type": "CallExpression",
              "start": 40,
              "end": 54,
              "callee": {
                "type": "MemberExpression",
                "start": 40,
                "end": 51,
                "object": {
                  "type": "Identifier",
                  "start": 40,
                  "end": 47,
                  "name": "console"
                },
                "property": {
                  "type": "Identifier",
                  "start": 48,
                  "end": 51,
                  "name": "log"
                },
                "computed": false,
                "optional": false
              },
              "arguments": [
                {
                  "type": "Identifier",
                  "start": 52,
                  "end": 53,
                  "name": "a"
                }
              ],
              "optional": false
            }
          }
        ]
      }
    }
  ],
  "sourceType": "module"
}

参考
 掘金文章参考

20210731编译原理准备