Lexing and Parsing With Syntax Trees

Compileするときに使う構造に変換する(parse)必要があるので、それについて詳しく見ていきます。

CPythonではparseするためにどういった構造を使うか

• Concrete Syntax Tree(CST), known as a parse tree

• Abstract Syntax Tree(AST)

• Parse Process

  • 入力したテキストをLexer(parser-tokenizer)を使ってCSTにする
  • ParserでCSTをASTにする

Concrete Syntax Tree Generation

• ordered, rooted tree structure that represents code in a context-free grammar
• CSTはtokenizerとparserで作られる
• parser generatorは前の章でGrammarから作ったよ
• 決定性有限オートマトン(DFA)がParser Generatorの結果となり、context free grammarを受理するかを判定する
• CSTはtoken, terminal(leaf node)で表現される
• CSTの具体例：

  • a+1

    

    • term operator termみたいな分岐

    • 与えられた文章が文法にマッチしているか（Automatonが受理するか）をCSTを作って判定している

    • Grammar/Grammarに定義がかいてる

    • a+1を解釈するためのGrammar:

      arith_expr: term (('+'|'-') term)*
      term: factor (('*'|'@'|'/'|'%'|'//') factor)*
      factor: ('+'|'-'|'~') factor | power
      power: atom_expr ['**' factor]
      atom_expr: [AWAIT] atom trailer*
      atom: ('(' [yield_expr|testlist_comp] ')' |
             '[' [testlist_comp] ']' |
             '{' [dictorsetmaker] '}' |
             NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False')
      

    • Tokens

      ENDMARKER
      NAME
      NUMBER
      STRING
      NEWLINE
      INDENT
      DEDENT
      
      LPAR                    '('
      RPAR                    ')'
      LSQB                    '['
      RSQB                    ']'
      COLON                   ':'
      COMMA                   ','
      SEMI                    ';'
      PLUS                    '+'
      MINUS                   '-'
      STAR                    '*'
      

    • symbol, token moduleでGrammarとTokensの定義をpython 上で見ることができる

CPython Parser Tokenizer

parser-tokenizer(lexer)の実装を見ていく

• 見るソース
  • Python/pythonrun.c
  • Parser/parsetok.c
  • Parser/tokenizer.c
  • Parser/tokenizer.h
  • Include/token.h
  • Include/node.h