5

これは私の 3 年次プログラミング言語クラスの宿題であり、そのための助けを求めていることを前置きしたいと思います。私の課題は次のとおりです。

締め切り: 2013 年 2 月 22 日午後 11 時 55 分
提出: 以下を CMS にアップロードしてください。

1. ソース コード
2. 使用した入力ファイルを含むプログラム実行のスクリーン ショット

次の EBNF 記述によって生成された言語を解析する再帰降下パーサーを作成するには、任意のプログラミング言語を使用してください。パーサーは、入力プログラムに構文エラーがあるかどうかを検出する必要があります。エラーの内容と場所を特定する必要はありません。

<program>   begin <stmt_list> end
<stmt_list>  <stmt> {;<stmt_list>}
<stmt>    <assign_stmt> | <while_stmt>
<assign_stmt>  <var> = <expr>
<var>  identifier  (An identifier is a string that begins with a letter followed by 0     or more letters and digits)
<expr>  <var> { (+|-) <var>}           
<while_stmt>   while (<logic_expr>)  <stmt>
<logic_expr> ® <var> (< | >) <var>  (Assume that logic expressions have only less than     or greater than operators)

変に見える記号は、右向きの矢印だけです。

現時点での私の問題は、プログラミングよりも論理的です。最初の試みで、入力プログラム全体を読み取り、文字列に保存し、その文字列を解析して、すべての記号を端末、expr、またはあなた。

最終的に、この方法は機能しないことがわかりました。A: RDP ではないと思います。B: 非端末の多くは 1 つ以上のステートメントで構成されています。

私はそのアプローチをあきらめ、プログラミングにこれ以上時間を費やす前に、すべてを疑似的に処理することにしました。私の新しいアイデアは、非終端記号ごとに 1 つのメソッドを作成し、それらのメソッドの間で期待して、入力文字列記号を記号ごとに解析することでした。このアプローチは論理的に思えましたが、疑似コードを書き始めると、何をする必要があるかについて非常に迷い、混乱しました。 このコードをどのように仕上げますか?

RDP の擬似コードを次に示します。

intputString;

public void parseProgram (Symbol.typeIsProgram) {
    if getNextSymbol == "begin" {
        if (intputString.substring (inputString.length()-3,
                inputString.length()) == "end") {
            Symbol stmt_lsit = new Symbol (intputString)
            parseStmt_list(stmt_list);              
        } else {
            Out "error, prog must end with end"
        }
    } else {
        Out "error, prog must begin with begin"
    }   
}

public void parseStmt_list (Stmbol.typeIsStmt_list) {
    symbol = getNextSymbol;
    if (Symbol.typeIsVar) {
        parseVar(symbol)
    } else if (Symbol.typeIsWhile)  {
        // weve only capture if the first word return is a while, we dont have the whole while statement yet
        ParseWhile_stmt(symbol)
    } else { }
}

public void parseStmt () { }
public void parseAssign_stmt () { }
public void parseVar () { }
public void parseExpr () { }
public void parseWhile_stmt () { }
public void parseLogic_expr () { }

public Symbol getNextSymbol() {
    //returns the next symbol in input string and removes it from the input string
}

参考までに、パーサーのサンプル入力プログラムは次のようになります。

begin 
total = var1 + var2; 
while (var1 < var2) 
while ( var3 > var4)
var2 = var2 - var1 
end
4

3 に答える 3

7

この特定の割り当てによれば、機能的な方法で文字列処理を使用することは問題ありません。

このアルゴリズムを試してください：

  1. チェック、その行はで始まり、beginで終わるend
  2. はいの場合-残りの文字列をで分割;し、各部分に対して次の手順を実行します（ステートメント）
  3. ステートメントが=またはwhile部分文字列で構成されているかどうかを確認します
  4. +割り当てチェックの場合は、またはで入力を分割でき-、各部分の可変条件（英数字コンテンツ）をチェックします。
  5. for while-ブラケットの間とその後の2つの文字列をチェックし(、)再帰的に処理します
  6. 最後に、部分文字列<または>で分割された論理式の場合、パーツが変数（英数字）であることを確認します

たぶん、それはあまり柔軟な解決策ではありませんが、私が見るように、それはあなたの仕事に受け入れられます。

編集：

私はそのタスクが面白いと感じ、完全な解決策を書こうとしました。

public enum Parser {
PROGRAM {
    void parse(String s) throws ParseException {
        s = s.trim();
        if (s.startsWith("begin") && s.endsWith("end")) {
            STATEMENT_LIST.parse(s.substring(5, s.length() - 3));
        } else {
            throw new ParseException("Illegal begin/end");
        }
    }
},

STATEMENT_LIST {
    void parse(String s) throws ParseException {
        String[] parts = s.trim().split(";");
        for (String part : parts) {
            STATEMENT.parse(part.trim());
        }
    }
},

STATEMENT {
    void parse(String s) throws ParseException {
        if (s.startsWith("while")) {
            WHILE.parse(s.substring(5));
        } else if (s.contains("=")) {
            ASSIGNMENT.parse(s);
        } else {
            throw new ParseException("Illegal statement: " + s);
        }
    }
},

WHILE {
    void parse(String s) throws ParseException {
        int i = s.indexOf("(");
        int j = s.indexOf(")");
        if (i != -1 && j != -1) {
            LOGICAL.parse(s.substring(i + 1, j).trim());
            STATEMENT.parse(s.substring(j + 1).trim());
        } else {
            throw new ParseException("Illegal while: " + s);
        }
    }
},

ASSIGNMENT {
    void parse(String s) throws ParseException {
        int i = s.indexOf("=");
        if (i != -1) {
            VARIABLE.parse(s.substring(0, i).trim());
            EXPRESSION.parse(s.substring(i + 1).trim());
        }
    }
},

EXPRESSION {
    void parse(String s) throws ParseException {
        String[] parts = s.split("\\+|-");
        for (String part : parts) {
            VARIABLE.parse(part.trim());
        }
    }
},

LOGICAL {
    void parse(String s) throws ParseException {
        int i;
        if (s.contains("<")) {
            i = s.indexOf("<");
        } else if (s.contains(">")) {
            i = s.indexOf(">");
        } else {
            throw new ParseException("Illegal logical: " + s);
        }

        VARIABLE.parse(s.substring(0, i).trim());
        VARIABLE.parse(s.substring(i + 1).trim());
    }
},

VARIABLE {
    void parse(String s) throws ParseException {
        if (!s.matches("^[a-zA-Z][a-zA-Z0-9]*$")) {
            throw new ParseException("Illegal variable: " + s);
        }
    }
};

abstract void parse(String s) throws ParseException;

public static void main(String[] args) {
    try {
        PROGRAM.parse("begin \n" +
                "total = var1 + var2; \n" +
                "while (var1 < var2) \n" +
                "while ( var3 > var4)\n" +
                "var2 = var2 - var1 \n" +
                "end");
        System.out.println("OK");
    } catch (ParseException e) {
        System.out.println(e.getMessage());
    }
}
}

class ParseException extends Exception {
public ParseException(String message) {
    super(message);
}
}
于 2013-02-16T19:30:25.780 に答える
4

1) トークン化

最初に入力をトークンに分割します。この場合、すべての識別子と演算子とリテラル。すべての入力トークンの大きなリストを作成します。トークンを取得したら、解析を開始できます。トークンをリンクされたリストにすると、Token.Next と言って次のトークンを読み取るか、Token.Next.Next と言って 2 つ先のトークンを読み取ることができます。最後にたくさんの EOF トークンを配置して、それをスキップしないようにします。

2) 解析

解析は、すでに持っているもののようなものです。したがって、シンボルを考える代わりに、トークンを考えてください。構文解析リストは、最後まで構文解析を続ける while ループです。

解析ステートメントの場合

public void parseStmt ()
{
  if (Token.kind == KEYWORD && Token.id == kw_while) {
    return ParseWhileStatement();
  }
  else {
    return ParseAssignStatement();
  }
}

while ステートメントを解析すると、parse ステートメントにループバックされるため、「再帰的に下降」して Parse ステートメントに戻り、ネストされた while ループなどが生成されます...

割り当てステートメントの解析は非常に似ています。左側を解析し、次に右側を解析します。そのためにはたくさんの関数が必要です....

ここでの Node は、Ast ノードです。抽象構文ツリー。

みたいなもの...

class Node {

}
class OpNode {
  OpNode Lhs;
  OpNode Rhs;
}
class MultiplyNode : OpNode {
  MultiplyNode(byref Token tok, OpNode Left, OpNode right) {
    tok = tok.Next;
    Lhs = left;
    Rhs = right;
  }
}




Node ParseSimpleExp() {
  if (Token.kind == Identifier) {
    Node n = new IdentNode;
    NextToken();
    return n;
  }
  if (Token.kind == Number) {
    Node n = new NumberNode;
    NextToken();
    return n;
  }
}


// In these examples move the token to next token when you create the new nodes
Node ParseMulExp() {
  Node n = ParseSimpleExp();
  while (1) {
    if (Token.Kind == Multiply) {
      n = new MultiplyNode(Token,n,ParseSimpleExp());
      continue;
    }
    if (Token.Kind == Divide) {
      n = new DivideNode(Token,n,ParseSimpleExp());
      continue;
    }
    return n;
 }
}

Node ParseAddExp() {
  Node n = ParseMulExp();
  while (1) {
    if (Token.Kind == Add) {
      n = new AddNode(Token,n,ParseMulExp());
      continue;
    }
    if (Token.Kind == Subtract) {
      n = new SubtractNode(Token,n,ParseMulExp());
      continue;
    }
    return n;
  }
}


Node ParseAssignStatement() {
  Node n = ParseAddExp();
  if (Token.kind == ASSIGN) {
    return new AssignStatement(Token,n,ParseAddExp());
  }
}

ロジックに従うと、各ターゲットに再帰的に到達することで、優先ルールがどのように守られるかを確認できます。式の解析と代入からの開始はループではありません。ここに示されているようなものです。明らかにこれは単純すぎますが、テクニックを示しています。

したがって、RDP は、現在のトークンを見て、トークンを処理する関数にジャンプすることによって発生します。当然、これは同じ関数に戻る可能性があるため、再帰的です。ParseSimpleExp 関数を見ると、括弧で囲まれた式を処理するのに適した場所であることがわかります。parens 式は単純な exp への再帰を引き起こし、mul や add のような他のすべての可能性があります。

于 2013-02-16T19:22:24.160 に答える
1

パーサー コードの構造は、言語構文の構造に似ている必要があります。例えば

 <program>  ::= begin <stmt_list> end

のようなものに変換されます

function parse_program() {
  parse_begin();
  repeat parse_stmt();
  parse_end();
}

トークンの処理 (スキャナー) と構造の解析 (パーサー) を混同しないでください。

エラー処理の if / else 構造ではなく、例外処理を使用します。適切なエラー メッセージを表示するために、ソース (スキャナー) パーツのどこにいるかを追跡したい場合があります。スキャナにその状態を尋ねるだけです。

幸いなことに、割り当てには競合の解決が必要ないように思われるため、再帰的な適切な機能がうまく機能するはずです。興味深い部分は、

<while_stmt> ::= while (<logic_expr>)  <stmt>

parse_stmt()再帰的に呼び出すことになります。これが、再帰的降下解析の全体的な考え方です。

于 2013-02-16T19:17:47.377 に答える