Java中的遞歸下降解析器

Question

我想說這是我的第三年編程語言類的家庭作業，我正在尋找一些幫助。我的任務寫着：

截止日期：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 ，或者你有什麼。

我終於發現這種方式是行不通的，因爲答：我不認爲它是RDP，B：很多非終端是由多於一個語句組成的。

我放棄了這種方法，並決定在浪費更多時間進行編程之前，我會把所有東西都僞裝出來。我的新想法是爲每個非終結符號製作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 

Answer 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()遞歸。這就是遞歸下降解析的全部想法。

Answer 2

1）標記化

首先將輸入分解爲標記。在這種情況下，每個標識符和操作符和文字。列出所有輸入令牌的大名單。一旦你有令牌，你就可以開始解析。將令牌設置爲鏈接列表，以便您可以說Token.Next讀取下一個令牌或Token.Next.Next以讀取前面的2個令牌。在最後放置一堆EOF標記，以便永遠不會跳過它。

2）解析

解析就像你已經。所以，而不是思考符號思考令牌。 Parse Statements列表是一個while循環，它保持分析語句直到結束。

對於解析聲明

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

解析while語句將循環回解析的語句，因此它將「遞歸下降」回解析的語句，產生嵌套while循環等等

解析該賦值語句非常相似。分析左側，然後右側。你需要一堆功能....

這裏的節點是一個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一樣。

Answer 3

根據這個特定的賦值，可以以函數方式使用字符串處理。

試試這個算法：

1. 檢查，該行開始begin與end
2. 結束，如果是 - 分裂剩餘字符串;並執行以下步驟爲每個部分（聲明）
3. 檢查語句是否包含=或while子串
4. 分配檢查您可以將輸入與+或-並且對於每個部分檢查變量條件（字母數字內容）
5. 用於在 - 檢查(和)遞歸處理括號之間和之後
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); 
} 
}