compiler construction 解析 トークンとレクセムの違いは何ですか?




構文 解析 結果 (8)

Aho UllmanとSethiによるコンパイラ構築では、ソースプログラムの入力文字列が論理的意味を持つ文字列に分割され、トークンとして知られており、レクメムはトークンを構成するシーケンスなので基本的な違いは何ですか?


字句解析ツール(Scannerとも呼ばれます)の動作を見てみましょう。

例を見てみましょう:

INPUT : cout << 3+2+3;

FORMATTING PERFORMED BY SCANNER :  {cout}|space|{<<}|space|{3}{+}{2}{+}{3}{;} 

実際の出力ではありません。

SCANNERは、入力が無制限になるまで、ソースプログラムテキストでのレシートを繰り返し表示します

Lexemeは文法に存在する有効な文字列を形成する入力の部分文字列です。 すべての語彙素は、最後に説明されているパターン (最後に読者がスキップする可能性がある部分)

(重要なルールは、次の空白に遭遇するまで有効な文字列を形成する可能な最長の接頭辞を探すことです...以下で説明します)

LEXEMES:

  1. コウト
  2. <<

(ただし、 "<"も有効な端末文字列ですが、上記ルールはスキャナによって返されたトークンを生成するために字句 "<<"のパターンを選択します)

  1. 3
  2. +
  3. 2
  4. ;

TOKENS: Scannerが(有効な)語彙素を見つけられるたびに、トークンは1回につき1つずつ返されます(Parserの要求に応じてScannerによって返されます)。 スキャナーは、 トークンを生成するために、字句が見つかった場合に、シンボルテーブルエントリ(属性:主にトークンカテゴリおよびその他のものを含む)をまだ作成していない場合は作成します

'#'はシンボルテーブルエントリを示します。 理解を容易にするために上記リストの語彙番号を指摘しましたが、技術的にはシンボルテーブルの実際の索引でなければなりません。

上記の例では、以下のトークンが指定された順序でスキャナからパーサに返されます。

  1. <識別子、#1>

  2. <演算子、#2>

  3. <Literal、#3>

  4. <演算子、#4>

  5. <Literal、#5>

  6. <演算子、#4>

  7. <Literal、#3>

  8. <穿刺器、#6>

違いを見ることができるので、トークンは入力の部分文字列である字句とは異なり、ペアです。

ペアの最初の要素はトークンクラス/カテゴリです

トークンクラスは次のとおりです。

  • キーワード
  • 身分証明書
  • リテラル
  • パンチ
  • オペレーター
  • さらにもう一つ、スキャナは空白を検出し、それを無視し、空白のためのトークンをまったく形成しません。 すべての区切り文字が空白文字であるわけではありませんが、空白文字はその目的のためにスキャナによって使用される区切り文字の1つの形式です。 タブ、改行、スペース、エスケープされた文字はすべて空白区切りと呼ばれます。 いくつかの区切り文字は ';' '、' ':'などであり、トークンを構成する語彙素として広く認識されている。

    返されるトークンの総数はここでは8ですが、6つのシンボルテーブルエントリのみがレクエムに対して作成されます。 Lexemesも合計で8です(字句の定義を参照)

    ---この部分をスキップすることができます

    A ***pattern*** is a rule ( say, a regular expression ) that is used to check if a string-of-terminals is valid or not

    If a substring of input composed only of grammar terminals is following the rule specified by any of the listed patterns , it is validated as a lexeme and selected pattern will identify the category of lexeme, else a lexical error is reported due to either (i) not validated as a lexeme and selected pattern will identify the category of lexeme, else a lexical error is reported due to either (i) not validated as a lexeme and selected pattern will identify the category of lexeme, else a lexical error is reported due to either (i) not following any of the rules or (ii) input consists of a bad terminal-character not present in grammar itself. following any of the rules or (ii) input consists of a bad terminal-character not present in grammar itself. following any of the rules or (ii) input consists of a bad terminal-character not present in grammar itself.

    for example :
    
    1. No Pattern Exists : In C++ , "99Id_Var" is grammar-supported string-of-terminals but is not recognised by any of patterns hence lexical error is reported .
    
    2. Bad Input Character : $,@,unicode characters may not be supported as a valid character in few programming languages.`
    

    Lexemeは基本的にトークンの単位であり、基本的にトークンと一致する文字列であり、ソースコードをトークンに分解するのに役立ちます。

    例:ソースがx=bならば、レクエムはx=bとなり、トークンは<id, 0><=><id, 1>


    トークン:(キーワード、識別子、句読点、複数文字の演算子)の種類は、単純にトークンです。

    パターン:入力文字からトークンを形成するためのルール。

    レキシマス(Lexeme):SOURCE PROGRAM内の文字列で、トークンのパターンと一致します。 基本的に、トークンの要素。


    Lexeme - 語彙は、プログラミング言語の最も低いレベルの構文単位である文字列です。

    トークン - トークンは、語彙クラスがどのようなクラスに属しているかを表す構文クラスであり、キーワードまたは識別子などである。 字句アナライザの主なタスクの1つは、すべての文字を収集するために、字句とトークンのペアを作成することです。

    例を挙げてみましょう:

    if(y <= t)

    y = y-3;

    レクセムトークン

    KEYWORD

    (LEFT PARENTHESIS

    身分証明書

    <=比較

    身分証明書

    )右の親戚

    身分証明書

    =アサーション

    身分証明書

    _合理的

    3 INTEGER

    ; セミコロン

    レキシマスとトークンの関係


    レクエム (lexeme) - レクメムは、ソースプログラム内の文字列であり、トークンのパターンと一致し、そのトークンのインスタンスとしてレキシカルアナライザによって識別されます。

    トークン - トークンは、トークン名とオプションのトークン値からなるペアです。 トークン名は、語彙単位のカテゴリです。共通トークン名は次のとおりです。

    • 識別子:プログラマが選択する名前
    • キーワード:既にプログラミング言語で使用されている名前
    • 区切り記号(句読点とも呼ばれます):区切り文字とペア区切り記号
    • 演算子:引数に作用し結果を生成するシンボル
    • リテラル:数値、論理、テキスト、参照リテラル

    この表現をプログラミング言語Cで考えてみましょう。

    sum = 3 + 2;

    トークン化され、次の表で表されます。

     Lexeme        Token category
    ------------------------------
    sum      |    Identifier
     =       |    Assignment operator
     3       |    Integer literal
     +       |    Addition operator
     2       |    Integer literal
     ;       |    End of statement
    

    Aho、Lam、Sethi、Ullmanの " Compilers Principles、Techniques、&Tools、2nd Ed。 " (WorldCat) 、AKA the Purple Book

    Lexeme pg。 111

    字句は、トークンのパターンと一致し、そのトークンのインスタンスとして語彙アナライザによって識別されるソースプログラム内の文字シーケンスです。

    トークンpg。 111

    トークンはトークン名とオプションの属性値からなるペアです。 トークン名は、語彙単位の種類、例えば特定のキーワード、または識別子を示す入力文字列を表す抽象的な記号である。 トークン名は、パーサーが処理する入力シンボルです。

    パターンpg。 111

    パターンとは、トークンの語彙が取り得る形式の記述です。 トークンとしてのキーワードの場合、パターンは単にキーワードを形成する文字のシーケンスです。 識別子やその他のトークンについては、パターンはより複雑な構造であり、多くの文字列と一致します。

    図3.2:トークンの例pg.112

    [Token]       [Informal Description]                  [Sample Lexemes]
    if            characters i, f                         if
    else          characters e, l, s, e                   else
    comparison    < or > or <= or >= or == or !=          <=, !=
    id            letter followed by letters and digits   pi, score, D2
    number        any numeric constant                    3.14159, 0, 6.02e23
    literal       anything but ", surrounded by "'s       "core dumped"
    

    レクサーとパーサーとのこの関係をよりよく理解するために、パーサーから始めて入力に向かって作業を進めます。

    パーサーを簡単に設計するために、パーサーは入力と直接関係しませんが、レクサーによって生成されたトークンのリストを取り込みます。 図3.2のトークン列を見るcomparisonifelsecomparisonidnumberliteralなどのトークンがあります。 これらはトークンの名前です。 通常、トークンは、トークンの名前だけでなくトークンを構成する文字/記号、トークンを構成する文字列の開始位置と終了位置を保持する構造体です。エラーの報告、強調表示などに使用される開始位置と終了位置

    次に、レクサーは文字/記号の入力を受け取り、レクサーの規則を使用して、入力された文字/記号をトークンに変換する。 これで、レクサー/パーサを扱う人々は、頻繁に使うことのために自分の言葉を持っています。 あなたがトークンを構成する一連の文字/記号として考えるものは、字句解析器を使用する人々が字句を呼び出すものです。 だから、字句を見るときは、単にトークンを表す文字/記号のシーケンスを考えてみてください。 比較例では、文字/記号のシーケンスは、 < or >またはelseまたは3.14などの異なるパターンにすることができます。

    2つの間の関係を考えるもう一つの方法は、トークンは、入力から文字/記号を保持するlexemeというプロパティを持つパーサによって使用されるプログラミング構造です。 コード内のトークンのほとんどの定義を見ると、トークンのプロパティのうちの一部であるレキシマスが見えない場合があります。 これは、トークンがトークンと字句を表す文字/記号の開始位置と終了位置を保持する可能性が高いため、入力が静的であるため、文字/記号のシーケンスは必要に応じて開始位置と終了位置から導き出すことができるからです。


    a)トークンは、プログラムのテキストを構成するエンティティの記号名です。 例えばキーワードifの場合はid、任意の識別子の場合はid。 これらは字句分析器の出力を構成します。 5

    (b)パターンは、入力からの文字列がいつトークンを構成するかを指定する規則である。 例えば、トークンiのためのシーケンスi、fと、トークンidの文字で始まる任意のシーケンスの英数字。

    (c)字句は、パターンに一致する(したがってトークンのインスタンスを構成する)入力からの一連の文字である。 ifはifのパターンと一致し、foo123barはidのパターンと一致します。


    トークン:トークンは、単一の論理エンティティとして扱うことができる一連の文字です。 典型的なトークンは、
    1)識別子
    2)キーワード
    3)演算子
    4)特殊記号
    5)定数

    パターン:同じトークンが出力として生成される入力内の文字列のセット。 この一連の文字列は、トークンに関連付けられたパターンと呼ばれるルールによって記述されます。
    レキシマス (lexeme) レクメムは、ソースプログラム内でトークンのパターンと一致する一連の文字です。





    compilation