/var/log/messages

Aug 15, 2018 - 2 minute read - Comments - programming

再帰下降構文解析器

基本的な考え方と構造、について自分メモを以下に控え。

疑似コードを写経してみる。

function parseProgram() {
  program = newProgramASTNode()

  advanceTokens()

  for (currentToken() != EOF_TOKEN) {
    statement = null

    if (currentToken() == LET_TOKEN) {
      statement = parseLetStatement()
    } else if (currentToken() == RETURN_TOKEN) {
      statement = parseReturnStatement()
    } else if (currentToken() == IF_TOKEN) {
      statement = parseIfStatement()
    }

    if (statement != null) {
      program.Statements.push(statement)
    }

    advanceTokens()
  }

  return program
}

function parseLetStatement() {
  advanceTokens()

  identifier = parseIdentifier()

  advanceTokens()

  if currentToken() != EQUAL_TOKEN {
    parseError("no equal sign!")
    return null
  }

  advanceTokens()

  value = parseExpression()

  variableStatement = newVariableStatementASTNode()
  variableStatement.identifier = identifier
  variableStatement.value = value
  return variableStatement
}

function parseIdentifier() {
  identifier = newIdentifierASTNode()
  identifier.token = currentToken()
  retunr identifier
}

function parseExpression() {
  if (currentToken() = INTEGER_TOKEN) {
    if (nextToken() == PLUS_TOKEN) {
      return parseOperatorExpression()
    } else if (nextToken() == SEMICOLON_TOKEN) {
      return parseIntegerLiteral()
    }
  } else if (currentToken() == LEFT_PAREN) {
    return parseGroupedExpression()
  }
// [...]  
}

function parseOperatorExpression() {
  operatorExpression = newOperatorExpression()

  operatorExpression.left = parseIntegerLiteral()
  operatorExpression.right = parseExpression()

  return operatorExpression()
}
// [...]
  • エントリポイントは parseProgram
  • この中で AST の root node を newProgramASTNode で生成
  • EOF になるまで token を parse していきます
  • parse した結果は program に追加される

そして再帰、なキモ、って意味では parseExpression が中心になる、とのこと。定義によれば数値な token の次に + な token が存在する場合は以降を parseExpression で構文解析を行なっていることがわかります。これは

1 + 2 + 3

な式は

((1 + 2) + 3)

みたいなカンジで、なのかどうか

parser_test.go 関連

以下な諸々確認してみます。

    l := lexer.New(input)
    p := New(l)

    program := p.ParseProgram()

ParseProgram の定義が以下なんですが

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

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

    return program
}

戻りなオブジェクトの用意をしておいて Parser が持ってる token を取り出して AST なオブジェクトを、なんですが append って何だろう、と思ったら組込みな手続きで追加なナニが用意されているようですね。

テスツ的には let 文が三つなので、なのかどうか。

字句解析器のためのテスト

最初に出てくるサンプルてきに

  • test 対象のソースを parser に渡して ParseProgram して *ast.Program を生成
  • Statements を確認
  • 文が正常かどうかを確認 (testLetStatement)
  • Let として正常かを確認する場合、試験対象の TokenLiteral がどうか
  • 試験対象のオブジェクトとしてキャストできるか
  • Name 属性の Token 属性のチェック
  • Name 属性の Value 属性のチェック

というのが定型、ということなのかどうか。

Dlv scheme 実装

comments powered by Disqus