构建解析器(第一部分)

Question

我正在制作我自己的基于javascript的编程语言(是的,它很疯狂,但这只是为了学习...... 也许？).好吧,我正在阅读解析器,第一步是将代码源转换为令牌,如:

if(x > 5)
  return true;

Tokenizer:

T_IF          "if"
T_LPAREN      "("
T_IDENTIFIER  "x"
T_GT          ">"
T_NUMBER      "5"
T_RPAREN      ")"
T_IDENTIFIER  "return"
T_TRUE        "true"
T_TERMINATOR  ";"

我不知道我的逻辑是否正确.在我的解析器上它甚至更好(或不是？)并转换为它(是的,多维数组):

T_IF             "if"
  T_EXPRESSION     ...
    T_IDENTIFIER     "x"
    T_GT             ">"
    T_NUMBER         "5"
  T_CLOSURE        ...
    T_IDENTIFIER     "return"
    T_TRUE           "true"

我有些疑惑:

1. 原来的方式是我的方式更好还是更差？请注意,我的代码将被读取和编译(翻译成另一种语言,如PHP),而不是一直解释.
2. 在我令牌化之后,我需要做什么呢？我真的迷失了这个传球!
3. 有一些很好的教程可以学习如何做到这一点？

好吧,就是这样.再见!

Answer 1

通常,您希望将tokenizer(也称为lexer)的函数与编译器或解释器的其他阶段分开.其原因是基本模块化:每个传递消耗一种事物(例如,字符)并产生另一种事物(例如,令牌).

所以你已经将你的角色转换为代币.现在,您希望将令牌的平面列表转换为有意义的嵌套表达式,这就是传统上称为解析的内容.对于类似JavaScript的语言,您应该研究递归下降解析.对于使用不同优先级的中缀运算符解析表达式,Pratt解析非常有用,并且对于特殊情况,您可以回退到普通的递归下降解析.

为了给你一个基于你的案例的更具体的例子,我假设你可以写两个函数:accept(token)并且expect(token),它测试你创建的流中的下一个标记.您将为您的语言语法中的每种语句或表达式创建一个函数.这是statement()函数的Pythonish伪代码,例如:

def statement():

  if accept("if"):
    x = expression()
    y = statement()
    return IfStatement(x, y)

  elif accept("return"):
    x = expression()
    return ReturnStatement(x)

  elif accept("{")
    xs = []
    while True:
      xs.append(statement())
      if not accept(";"):
        break
    expect("}")
    return Block(xs)

  else:
    error("Invalid statement!")

这为您提供了所谓的程序抽象语法树(AST),然后您可以操作(优化和分析),输出(编译)或运行(解释).

Answer 2

大多数工具包将整个过程分成两个独立的部分

• lexer(又名令牌)
• 解析器(又名语法)

标记生成器将输入数据拆分为标记.解析器将仅对令牌"stream"进行操作并构建结构.

你的问题似乎集中在tokenizer上.但是你的第二个解决方案将语法分析器和标记器混合成一步.从理论上讲,这也是可能的,但对于初学者是多容易做到这一点,因为大多数其他工具/框架相同:保持步骤分开.

对于您的第一个解决方案:我会像这样将您的示例标记为:

T_KEYWORD_IF   "if"
T_LPAREN       "("
T_IDENTIFIER   "x"
T_GT           ">"
T_LITARAL      "5"
T_RPAREN       ")"
T_KEYWORD_RET  "return"
T_KEYWORD_TRUE "true"
T_TERMINATOR   ";"

在大多数语言中,关键字不能用作方法名称,变量名称等.这已经是在标记生成器的水平(反映T_KEYWORD_IF,T_KEYWORD_RET,T_KEYWORD_TRUE).

下一个级别将采用此流并 - 通过应用正式语法 - 将构建一些数据结构(通常称为AST - 抽象语法树),它可能如下所示:

IfStatement:
    Expression:
        BinaryOperator:
            Operator:     T_GT
            LeftOperand: 
               IdentifierExpression:
                   "x"
            RightOperand:
                LiteralExpression
                    5
    IfBlock
        ReturnStatement
            ReturnExpression
                LiteralExpression
                    "true"
    ElseBlock (empty)

手动实现解析器通常由一些框架完成.通过手工和高效实现类似的东西通常在一个学期的大部分时间在大学完成.所以你真的应该使用某种框架.

语法分析器框架的输入通常是某种BNF中的形式语法.你的"if"部分看起来像这样:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ;

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ;

BinaryExpression: LeftOperand BinaryOperator RightOperand;

....

这只是为了得到这个想法.正确解析像Javascript这样的真实世界语言并非易事.但好笑.

Answer 3

我的方法比原来的方法更好还是更差？请注意，我的代码将被读取和编译（翻译为另一种语言，如 PHP），而不是一直解释。

原来的方法是什么？有许多不同的方法来实现语言。我认为你的实际上很好，我曾经尝试自己构建一种语言，并将其翻译为 C#，即hack 编程语言。许多语言编译器都会翻译为中间语言，这很常见。

在我分词器之后，我到底需要做什么？我真的对这个关卡迷失了！

标记化后，您需要对其进行解析。使用一些好的词法分析器/解析器框架，例如Boost.Spirit或 Coco 或其他框架。有数百个。或者您可以实现自己的词法分析器，但这需要时间和资源。解析代码的方式有很多种，我一般采用递归下降解析。

接下来您需要进行代码生成。我认为这是最困难的部分。也有用于此目的的工具，但如果您愿意，您可以手动执行此操作，我尝试在我的项目中执行此操作，但它非常基本且有缺陷，这里和这里有一些有用的代码。

有一些很好的教程可以学习如何做到这一点吗？

正如我之前建议的，使用工具来做到这一点。有很多很好的、文档齐全的解析器框架。要了解更多信息，您可以尝试询问一些了解这方面知识的人。@DeadMG，在休息室 C++正在构建一种名为“Wide”的编程语言。你可以尝试咨询他。