whitespace - ANTLR 空白の質問 (典型的な質問ではありません)

Question

次の短い SmallC プログラムについて考えてみましょう。

#include "lib"
main() {
    int bob;
}

私の ANTLR 文法は、ANTLWorks で、Interpreter を使用しているときに行末 -> "Mac (CR)" を指定すると、問題なく認識されます。行末オプションを Unix (LF) に設定すると、文法は NoViableAltException をスローし、include ステートメントの終了後に何も認識しません。インクルードの最後に改行を追加すると、このエラーは消えます。これに使用しているコンピューターは Mac であるため、行末を Mac 形式に設定する必要があることは理にかなっていると考えました。代わりに、Linuxボックスに切り替えて、同じことを取得します。ANTLRWorks インタープリターボックスに何かを入力し、行末 Mac (CR) を選択しないと、上記の場合のように空白行が不十分であるという問題が発生し、さらに、各ステートメントブロックの最後のステートメントには、セミコロンに続く余分なスペース (つまり、bob の後; 上記)。

これらのバグは、解析したいコード入力ファイルで文法の Java バージョンを実行すると再び表示されます...

何が問題になる可能性がありますか？問題が、おそらくパーサーが理解できなかった/私の空白ルールに捕らえられなかった形式で、あまりにも多くの新しい行が存在することであったかどうかは理解できます。しかし、この場合、それは新しい行が不足しているという問題です。

私の空白宣言は次のとおりです。

WS      :   ( '\t' | ' ' | '\r' | '\n' )+   { $channel = HIDDEN; } ;

あるいは、これはあいまいさの問題が原因である可能性がありますか?

完全な文法ファイルは次のとおりです (ANTLR のデフォルトのエラー処理メカニズムをオーバーライドする最初のいくつかのブロックは無視してかまいません:

grammar SmallC;

options {
    output = AST ;  // Set output mode to AST
}

tokens {
    DIV = '/' ;
    MINUS   = '-' ;
    MOD = '%' ;
    MULT    = '*' ;
    PLUS    = '+' ;
    RETURN  = 'return' ;
    WHILE   = 'while' ;

    // The following are empty tokens used in AST generation
    ARGS ;
    CHAR ;
    DECLS ;
    ELSE ;
    EXPR ;
    IF ;
    INT ;
    INCLUDES ;
    MAIN ;
    PROCEDURES ;
    PROGRAM ;
    RETURNTYPE ;
    STMTS ;
    TYPEIDENT ;
}

@members { 
// Force error throwing, and make sure we don't try to recover from invalid input.
// The exceptions are handled in the FrontEnd class, and gracefully end the
// compilation routine after displaying an error message.
protected void mismatch(IntStream input, int ttype, BitSet follow) throws RecognitionException {
    throw new MismatchedTokenException(ttype, input);
} 
public Object recoverFromMismatchedSet(IntStream input, RecognitionException e, BitSet follow)throws RecognitionException {
    throw e;
}
protected Object recoverFromMismatchedToken(IntStream input, int ttype, BitSet follow) throws RecognitionException {
     throw new MissingTokenException(ttype, input, null);
}

// We override getErrorMessage() to include information about the specific
// grammar rule in which the error happened, using a stack of nested rules.
Stack paraphrases = new Stack();
public String getErrorMessage(RecognitionException e, String[] tokenNames) {
    String msg = super.getErrorMessage(e, tokenNames);
    if ( paraphrases.size()>0 ) {
        String paraphrase = (String)paraphrases.peek();
        msg = msg+" "+paraphrase;
    }
    return msg;
}

// We override displayRecognitionError() to specify a clearer error message,
// and to include the error type (ie. class of the exception that was thrown)
// for the user's reference. The idea here is to come as close as possible
// to Java's exception output.
public void displayRecognitionError(String[] tokenNames, RecognitionException e)
{
    String exType;
    String hdr;
    if (e instanceof UnwantedTokenException) {
        exType = "UnwantedTokenException";
    } else if (e instanceof MissingTokenException) {
        exType = "MissingTokenException";
    } else if (e instanceof MismatchedTokenException) {
        exType = "MismatchedTokenException";
    } else if (e instanceof MismatchedTreeNodeException) {
        exType = "MismatchedTreeNodeException";
    } else if (e instanceof NoViableAltException) {
        exType = "NoViableAltException";
    } else if (e instanceof EarlyExitException) {
        exType = "EarlyExitException";
    } else if (e instanceof MismatchedSetException) {
        exType = "MismatchedSetException";
    } else if (e instanceof MismatchedNotSetException) {
        exType = "MismatchedNotSetException";
    } else if (e instanceof FailedPredicateException) {
        exType = "FailedPredicateException";
    } else {
        exType = "Unknown";
    }

    if ( getSourceName()!=null ) {
        hdr = "Exception of type " + exType + " encountered in " + getSourceName() + " at line " + e.line + ", char " + e.charPositionInLine + ": "; 
    } else {
        hdr = "Exception of type " + exType + " encountered at line " + e.line + ", char " + e.charPositionInLine + ": "; 
    }
    String msg = getErrorMessage(e, tokenNames);
    emitErrorMessage(hdr + msg + ".");
}
}

// Force the parser not to try to guess tokens and resume on faulty input,
// but rather display the error, and throw an exception for the program
// to quit gracefully.
@rulecatch {
catch (RecognitionException e) {
    reportError(e);
    throw e;
} 
}

/*------------------------------------------------------------------
 * PARSER RULES
 *
 * Many of these make use of ANTLR's rewrite rules to allow us to
 * specify the roots of AST sub-trees, and to allow us to do away
 * with certain insignificant literals (like parantheses and commas
 * in lists) and to add empty tokens to disambiguate the tree 
 * construction
 *
 * The @init and @after definitions populate the paraphrase
 * stack to allow us to specify which grammar rule we are in when
 * errors are found.
 *------------------------------------------------------------------*/

args
@init { paraphrases.push("in these procedure arguments"); }
@after { paraphrases.pop(); }
        :   ( typeident ( ',' typeident )* )?   ->  ^( ARGS ( typeident ( typeident )* )? )? ;

body
@init { paraphrases.push("in this procedure body"); }
@after { paraphrases.pop(); }
        :   '{'! decls stmtlist '}'! ;

decls
@init { paraphrases.push("in these declarations"); }
@after { paraphrases.pop(); }
        :   ( typeident ';' )*  ->  ^( DECLS ( typeident )* )? ;

exp
@init { paraphrases.push("in this expression"); }
@after { paraphrases.pop(); }
        :   lexp ( ( '>' | '<' | '>=' | '<=' | '!=' | '==' )^ lexp )? ;

factor      :   '(' lexp ')'
        |   ( MINUS )? ( IDENT | NUMBER ) 
        |   CHARACTER
        |   IDENT '(' ( IDENT ( ',' IDENT )* )? ')' ;

lexp        :   term ( ( PLUS | MINUS )^ term )* ;

includes
@init { paraphrases.push("in the include statements"); }
@after { paraphrases.pop(); }
        :   ( '#include' STRING )*  ->  ^( INCLUDES ( STRING )* )? ;

main    
@init { paraphrases.push("in the main method"); }
@after { paraphrases.pop(); }
        :   'main' '(' ')' body ->  ^( MAIN body ) ;

procedure
@init { paraphrases.push("in this procedure"); }
@after { paraphrases.pop(); }
        :   ( proc_return_char | proc_return_int )? IDENT^ '('! args ')'! body ;

procedures  :   ( procedure )*  ->  ^( PROCEDURES ( procedure)* )? ;

proc_return_char
        :   'char'  ->  ^( RETURNTYPE CHAR ) ;

proc_return_int :   'int'   ->  ^( RETURNTYPE INT ) ;

// We hard-code the regex (\n)* to fix a bug whereby a program would be accepted
// if it had 0 or more than 1 new lines before EOF but not if it had exactly 1,
// and not if it had 0 new lines between components of the following rule.
program     :   includes decls procedures main EOF ;

stmt
@init { paraphrases.push("in this statement"); }
@after { paraphrases.pop(); }
        :   '{'! stmtlist '}'!
        |   WHILE '(' exp ')' s=stmt    ->  ^( WHILE ^( EXPR exp ) $s )
        |   'if' '(' exp ')' s=stmt ( options {greedy=true;} : 'else' s2=stmt )?    ->  ^( IF ^( EXPR exp ) $s ^( ELSE $s2 )? )
        |   IDENT '='^ lexp ';'! 
        |   ( 'read' | 'output' | 'readc' | 'outputc' )^ '('! IDENT ')'! ';'!
        |   'print'^ '('! STRING ( options {greedy=true;} : ')'! ';'! )
        |   RETURN ( lexp )? ';'    ->  ^( RETURN ( lexp )? ) 
        |   IDENT^ '('! ( IDENT ( ','! IDENT )* )? ')'! ';'!;

stmtlist    :   ( stmt )*   ->  ^( STMTS ( stmt )* )? ;

term        :   factor ( ( MULT | DIV | MOD )^ factor )* ;

// We divide typeident into two grammar rules depending on whether the
// ident is of type 'char' or 'int', to allow us to implement different
// rewrite rules in each case.
typeident   :   typeident_char | typeident_int ;

typeident_char  :   'char' s2=IDENT ->  ^( CHAR $s2 ) ;

typeident_int   :   'int' s2=IDENT  ->  ^( INT $s2 ) ;

/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

// Must come before CHARACTER to avoid ambiguity ('i' matches both IDENT and CHARACTER)
IDENT       :   ( LCASE_ALPHA | UCASE_ALPHA | '_' ) ( LCASE_ALPHA | UCASE_ALPHA | DIGIT | '_' )* ;

CHARACTER   :   PRINTABLE_CHAR
        |   '\n' | '\t' | EOF ;

NUMBER      :   ( DIGIT )+ ;

STRING      :   '\"' ( ~( '"' | '\n' | '\r' | 't' ) )* '\"' ;

WS      :   ( '\t' | ' ' | '\r' | '\n' | '\u000C' )+    { $channel = HIDDEN; } ;

fragment 
DIGIT       :   '0'..'9' ;

fragment
LCASE_ALPHA :   'a'..'z' ;

fragment
NONALPHA_CHAR   :   '`' | '~' | '!' | '@' | '#' | '$' | '%' | '^' | '&' | '*' | '(' | ')' | '-'
        |   '_' | '+' | '=' | '{' | '[' | '}' | ']' | '|' | '\\' | ';' | ':' | '\''
        |   '\\"' | '<' | ',' | '>' | '.' | '?' | '/' ; 

fragment
PRINTABLE_CHAR  :   LCASE_ALPHA | UCASE_ALPHA | DIGIT | NONALPHA_CHAR ;
fragment
UCASE_ALPHA :   'A'..'Z' ;

score 1 · Accepted Answer

コマンドラインから、次の警告が表示されます。

java -cp antlr-3.2.jar org.antlr.Tool SmallC.g 
warning(200): SmallC.g:182:37: Decision can match input such as "'else'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

ただし、レクサー/パーサーの生成は停止しません。

とにかく、問題: ANTLR のレクサーは、ファイル内で最初に検出されたレクサールールと一致しようとします。上記のトークンと一致しない場合は、次のレクサールールにたどり着きます。CHARACTERこれで、ルールの前にルールが定義されました。WSどちらも文字に一致します\n。\nがとしてトークン化されたため、Linux では動作しなかったのはそのためCHARACTERです。WSルールの前にルールを定義するCHARACTERと、すべて適切に機能します。

// other rules ...

WS
  :  ('\t' | ' ' | '\r' | '\n' | '\u000C')+ { $channel = HIDDEN; } 
  ;

CHARACTER   
  :  PRINTABLE_CHAR | '\n' | '\t' | EOF 
  ;

// other rules ...

テストクラスの実行:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
    public static void main(String[] args) throws Exception {
        String source = 
                "#include \"lib\"\n" + 
                "main() {\n" + 
                "   int bob;\n" + 
                "}\n";
        ANTLRStringStream in = new ANTLRStringStream(source);
        SmallCLexer lexer = new SmallCLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        SmallCParser parser = new SmallCParser(tokens);
        SmallCParser.program_return returnValue = parser.program();
        CommonTree tree = (CommonTree)returnValue.getTree();
        DOTTreeGenerator gen = new DOTTreeGenerator();
        StringTemplate st = gen.toDOT(tree);
        System.out.println(st);
    }
}

次の AST を生成します。

ここに画像の説明を入力

エラーメッセージなし。

ただし、文法の警告を修正し、ルールで一致することは決してないため\n、ルールから削除する必要があります。CHARACTERCHARACTER

もう 1 つ: レクサールールで明示的に定義せずに、パーサールール内にかなりの数のキーワードを混在させています。先着順レクサールールのため、これは注意が必要です。'if'誤ってIDENT. 次のようにするとよいでしょう:

IF : 'if';
IDENT : 'a'..'z' ... ; // After the `IF` rule!

whitespace - ANTLR 空白の質問 (典型的な質問ではありません)

1 に答える 1

Related

Reference