ChatGPT|AI自制编程语言-语法解析1

用户1904552

发布于 2025-02-27 10:28:07

5490

文章被收录于专栏：周末程序猿周末程序猿

继续《AI自制编程语言》系列语法解析部分，先温习编译器执行步骤如下：

编译器执行步骤

而本篇主要集中语义解析和AST树生成部分，还未实现求值（下一篇《语法解析1》实现求值功能）。

1、语法解析

前面已经完成了词法解析部分，现在已经把每个Token都拿到了，那么要组合规则，比如let a = 10生成的词法结构如下：

Type: LET, Value: let
Type: IDENT, Value: a
Type: ASSIGN, Value: =
Type: INT, Value: 10
Type: EOF, Value:

下一步就是将这些词法转换为语法，这里就包括两个部分：

判断语义的合法性，比如let a let a = 0这就是不合法
将token转换为一颗AST树，类似看下图

AST树样例

2、递归下降解析器

词法解析生成的Token结构如下：

type TokenType string

const (
 AND             TokenType = "AND"
 ASSIGN          TokenType = "ASSIGN"
 ASTERISK        TokenType = "ASTERISK"
    ... // 扩展
)

type Token struct {
 Type  TokenType
 Value string
}

那么如何将词法按照顺序组合可执行的单元呢？就可以用到递归下降解析器，递归下降解析器是一种自顶向下的解析方法，它从语法的开始符号开始，尝试将输入与语法的产生式进行匹配，这种解析器的名称来源于它的工作方式，它递归地下降到语法树的叶子节点，然后再返回到根节点。递归下降解析器的工作原理如下：

对于每个非终端符号，都有一个与之对应的函数，这个函数的任务是解析输入并生成对应的AST节点。
当解析器需要解析一个非终端符号时，它会调用与该非终端符号对应的函数。
这个函数会查看输入的下一个符号，并尝试将其与当前非终端符号的所有可能的产生式进行匹配。
如果找到了一个匹配的产生式，函数就会为每个产生式中的符号递归地调用对应的函数。
果所有的产生式都没有匹配，函数就会报告一个语法错误。
如果函数成功地匹配了一个产生式，并且所有的递归调用都成功返回，那么函数就会创建一个新的AST节点，并返回这个节点。
如果函数无法匹配任何产生式，或者任何一个递归调用失败，那么函数就会返回一个错误。

递归下降解析器的优点是它们相对简单，易于实现，而且可以生成详细的错误消息。然而，它们也有一些缺点：

首先，它们不能处理左递归的语法，因为这会导致无限递归。
其次，它们的性能可能不如其他类型的解析器，特别是对于大型输入。在实际使用中，递归下降解析器通常会与其他技术结合使用，以处理更复杂的语法和提高性能，例如，预测性解析器是一种改进的递归下降解析器，它使用查找表来预测下一个符号，从而避免了不必要的回溯。

3、定义Prompt

了解的大概的实现方案后，可以定义如下Prompt：

你是一个使用golang开发的资深的程序员，正在实现AST语法解析，其中要求如下： 

### 已经定义的词法解析数据结构
type TokenType string

const (
 AND             TokenType = "AND"
 ASSIGN          TokenType = "ASSIGN"
 ASTERISK        TokenType = "ASTERISK"
 ASTERISK_EQUALS TokenType = "ASTERISK_EQUALS"
 BACKTICK        TokenType = "BACKTICK"
 BANG            TokenType = "BANG"
 CASE            TokenType = "CASE"
 COLON           TokenType = "COLON"
 COMMA           TokenType = "COMMA"
 CONST           TokenType = "CONST"
 CONTAINS        TokenType = "CONTAINS"
 DEFAULT         TokenType = "DEFAULT"
 DEFINE_FUNCTION TokenType = "DEFINE_FUNCTION"
 DOTDOT          TokenType = "DOTDOT"
 ELSE            TokenType = "ELSE"
 EOF             TokenType = "EOF"
 EQ              TokenType = "EQ"
 FALSE           TokenType = "FALSE"
 FLOAT           TokenType = "FLOAT"
 FOR             TokenType = "FOR"
 FOREACH         TokenType = "FOREACH"
 FUNCTION        TokenType = "FUNCTION"
 GT              TokenType = "GT"
 GT_EQUALS       TokenType = "GT_EQUALS"
 IDENT           TokenType = "IDENT"
 IF              TokenType = "IF"
 ILLEGAL         TokenType = "ILLEGAL"
 IN              TokenType = "IN"
 INT             TokenType = "INT"
 LBRACE          TokenType = "LBRACE"
 LBRACKET        TokenType = "LBRACKET"
 LET             TokenType = "LET"
 LPAREN          TokenType = "LPAREN"
 LT              TokenType = "LT"
 LT_EQUALS       TokenType = "LT_EQUALS"
 MINUS           TokenType = "MINUS"
 MINUS_EQUALS    TokenType = "MINUS_EQUALS"
 MINUS_MINUS     TokenType = "MINUS_MINUS"
 MOD             TokenType = "MOD"
 NOT_CONTAINS    TokenType = "NOT_CONTAINS"
 NOT_EQ          TokenType = "NOT_EQ"
 NULL            TokenType = "NULL"
 OR              TokenType = "OR"
 PERIOD          TokenType = "PERIOD"
 PLUS            TokenType = "PLUS"
 PLUS_EQUALS     TokenType = "PLUS_EQUALS"
 PLUS_PLUS       TokenType = "PLUS_PLUS"
 POW             TokenType = "POW"
 QUESTION        TokenType = "QUESTION"
 RBRACE          TokenType = "RBRACE"
 RBRACKET        TokenType = "RBRACKET"
 REGEXP          TokenType = "REGEXP"
 RETURN          TokenType = "RETURN"
 RPAREN          TokenType = "RPAREN"
 SEMICOLON       TokenType = "SEMICOLON"
 SLASH           TokenType = "SLASH"
 SLASH_EQUALS    TokenType = "SLASH_EQUALS"
 STRING          TokenType = "STRING"
 SWITCH          TokenType = "SWITCH"
 TRUE            TokenType = "TRUE"
)

type Token struct {
 Type  TokenType
 Value string
}

### AST解析入口函数要求是输入是`Token`结构体数组，输出是AST树
### 使用递归下降解析器实现
### 可以支持LET，EQ等简单几种TokenType
### 支持打印AST树
### 给出测试用例和main函数

4、生成代码

GPT生成了代码和main函数执行的测试代码：

type Node interface {
 TokenLiteral() string
 String() string
}

type Statement interface {
 Node
 statementNode()
}

type Expression interface {
 Node
 expressionNode()
}

type Program struct {
 Statements []Statement
}

func (p *Program) TokenLiteral() string {
 if len(p.Statements) > 0 {
  return p.Statements[0].TokenLiteral()
 } else {
  return ""
 }
}

func (p *Program) String() string {
 var out bytes.Buffer

 for _, s := range p.Statements {
  out.WriteString(s.String())
 }

 return out.String()
}

type LetStatement struct {
 Token Token
 Name  *Identifier
 Value Expression
}

func (ls *LetStatement) statementNode()       {}
func (ls *LetStatement) TokenLiteral() string { return ls.Token.Value }
func (ls *LetStatement) String() string {
 var out bytes.Buffer

 out.WriteString(ls.TokenLiteral() + " ")
 out.WriteString(ls.Name.String())
 out.WriteString(" = ")

 if ls.Value != nil {
  out.WriteString(ls.Value.String())
 }

 out.WriteString(";")

 return out.String()
}

type Identifier struct {
 Token Token
 Value string
}

func (i *Identifier) expressionNode()      {}
func (i *Identifier) TokenLiteral() string { return i.Token.Value }
func (i *Identifier) String() string       { return i.Value }

type Parser struct {
 tokens  []Token
 current int
}

func NewParser(tokens []Token) *Parser {
 return &Parser{tokens: tokens}
}

func (p *Parser) parseProgram() *Program {
 program := &Program{}
 program.Statements = []Statement{}

 for p.currentToken().Type != EOF {
  stmt := p.parseStatement()
  if stmt != nil {
   program.Statements = append(program.Statements, stmt)
  }
  p.nextToken()
 }

 return program
}

func (p *Parser) parseStatement() Statement {
 switch p.currentToken().Type {
 case LET:
  return p.parseLetStatement()
 default:
  return nil
 }
}

func (p *Parser) parseLetStatement() *LetStatement {
 stmt := &LetStatement{Token: p.currentToken()}

 if !p.expectPeek(IDENT) {
  return nil
 }

 stmt.Name = &Identifier{Token: p.currentToken(), Value: p.currentToken().Value}

 if !p.expectPeek(ASSIGN) {
  return nil
 }

 // TODO: We're skipping the expressions until we encounter a semicolon
 for !p.currentTokenIs(SEMICOLON) {
  p.nextToken()
 }

 return stmt
}

func (p *Parser) currentToken() Token {
 return p.tokens[p.current]
}

func (p *Parser) nextToken() Token {
 p.current++
 return p.currentToken()
}

func (p *Parser) currentTokenIs(t TokenType) bool {
 return p.currentToken().Type == t
}

func (p *Parser) expectPeek(t TokenType) bool {
 if p.nextToken().Type == t {
  return true
 } else {
  return false
 }
}

func main() {
 input := `
 let x = 5;
 let y = 10;
 let foobar = 838383;
 `
 tokens := Lexer(input)
 parser := NewParser(tokens)

 program := parser.parseProgram()
 fmt.Println(program.String())
}

通过以上代码，结合之前词法解析生成的代码，就可以在工程下获得运行结果：