Как мой синтаксический анализатор ANTLR (не лексер) может инициировать лексическое включение (не соединение AST)?

На веб-сайте ANTLR описаны два подхода к реализации директив включения. Первый подход состоит в том, чтобы распознать директиву в лексере и включить файл лексически (поместив CharStream в стек и заменив его тем, который считывает новый файл); второй — распознать директиву в анализаторе, запустить вспомогательный анализатор для анализа нового файла и вставить AST, сгенерированный вспомогательным анализатором. Ни то, ни другое не совсем то, что мне нужно.

В языке, который я разбираю, распознавание директивы в лексере нецелесообразно по нескольким причинам:

  1. Не существует самостоятельного шаблона символов, который всегда означает «это директива включения». Например, Include "foo"; на верхнем уровне — это директива включения, но в Array bar --> Include "foo"; или Constant Include "foo"; слово Include является идентификатором.
  2. Имя включаемого файла может быть задано в виде строки или идентификатора константы, и такие константы могут быть определены с помощью произвольно сложных выражений.

Итак, я хочу вызвать включение из парсера. Но чтобы выполнить включение, я не могу запустить вспомогательный парсер и соединить AST вместе; Я должен склеить жетоны. Блок может начинаться с { в основном файле и заканчиваться на } во включаемом файле. Файл, включенный в функцию, может даже закрыть определение функции и запустить новое.

Похоже, мне понадобится что-то вроде первого подхода, но на уровне TokenStreams вместо CharStreams. Это жизнеспособный подход? Сколько состояний мне нужно будет хранить в стеке и как заставить синтаксический анализатор переключаться обратно на исходный поток токенов, а не завершать работу, когда он достигает EOF? Или есть лучший способ справиться с этим?

==========

Вот пример языка, демонстрирующий, что блоки, открытые в основном файле, могут быть закрыты во включаемом файле (и наоборот). Обратите внимание, что # перед Include требуется, когда директива находится внутри функции, но необязательна снаружи.

основная.инф:

[ Main;
  print "This is Main!";
  if (0) {
  #include "other.h";
  print "This is OtherFunction!";
];

другое.ч:

  } ! end if
];  ! end Main

[ OtherFunction;

antlr c# include antlr3
person Jesse McGrew    schedule 24.08.2012    source источник
comment
Этот язык создан для мазохистов?   -  person Damien_The_Unbeliever    schedule 24.08.2012
comment
Хе. Это Inform, язык для написания текстовых приключенческих игр. Англоязычный сайт Inform 7 (inform7.com) – это пример элегантных и удивительных вещей, которые вы можете сделать, когда ваш дизайн не ограничивается традиционными инструментами контекстно-свободного синтаксического анализа. К сожалению, я анализирую Inform 6, который является примером невыразимо ужасных вещей, которые вы можете сделать, когда ваш дизайн не ограничен традиционными инструментами контекстно-независимого анализа.   -  person Jesse McGrew    schedule 24.08.2012
comment
@BartKiers К счастью, нет: имя файла может быть только строкой в ​​кавычках или одним идентификатором, который был определен ранее с помощью Constant. Определение, данное Constant, должно быть константой времени компиляции, поэтому никаких вызовов функций. В языке также нет текстовых операторов, поэтому нет конкатенации, но он может дублировать другую константу: Constant FOO "file.h"; Constant BAR FOO; Include BAR;   -  person Jesse McGrew    schedule 24.08.2012
comment
Но директива Constant вообще может иметь сколь угодно сложные выражения, так как она обычно используется с числами: Constant FOO (BAR + 5 * BAZ); и т. д., поэтому обработка Constant в лексере нецелесообразна.   -  person Jesse McGrew    schedule 24.08.2012

Ответы (1)


arrow_upward
2
arrow_downward

Для каждого оператора Include есть возможность позволить вашему синтаксическому анализатору создать новый экземпляр вашего лексера и вставить эти новые токены, которые создает лексер, в индекс, в котором в данный момент находится синтаксический анализатор (см. метод insertTokens(...) в блоке @members синтаксического анализатора).

Вот краткая демонстрация:

Информ6.г

grammar Inform6;

options {
  output=AST;
}

tokens {
  STATS;
  F_DECL;
  F_CALL;
  EXPRS;
}

@parser::header {
  import java.util.Map;
  import java.util.HashMap;
}

@parser::members {
  private Map<String, String> memory = new HashMap<String, String>(); 

  private void putInMemory(String key, String str) {
    String value;
    if(str.startsWith("\"")) {
      value = str.substring(1, str.length() - 1);
    }
    else {
      value = memory.get(str);
    }
    memory.put(key, value);
  }

  private void insertTokens(String fileName) {
    // possibly strip quotes from `fileName` in case it's a Str-token
    try {
      CommonTokenStream thatStream = new CommonTokenStream(new Inform6Lexer(new ANTLRFileStream(fileName)));
      thatStream.fill();
      List extraTokens = thatStream.getTokens();
      extraTokens.remove(extraTokens.size() - 1); // remove EOF
      CommonTokenStream thisStream = (CommonTokenStream)this.getTokenStream();
      thisStream.getTokens().addAll(thisStream.index(), extraTokens);
    } catch(Exception e) {
      e.printStackTrace();
    }
  }
}

parse
 : stats EOF -> stats
 ;

stats
 : stat* -> ^(STATS stat*)
 ;

stat
 : function_decl
 | function_call
 | include
 | constant
 | if_stat
 ;

if_stat
 : If '(' expr ')' '{' stats '}' -> ^(If expr stats)
 ;

function_decl
 : '[' id ';' stats ']' ';' -> ^(F_DECL id stats)
 ;

function_call
 : Id exprs ';' -> ^(F_CALL Id exprs)
 ;

include
 : Include Str ';' {insertTokens($Str.text);}            -> /* omit statement from AST */
 | Include id ';'  {insertTokens(memory.get($id.text));} -> /* omit statement from AST */
 ;

constant
 : Constant id expr ';' {putInMemory($id.text, $expr.text);} -> ^(Constant id expr)
 ;

exprs
 : expr (',' expr)* -> ^(EXPRS expr+)
 ;

expr
 : add_expr
 ;

add_expr
 : mult_expr (('+' | '-')^ mult_expr)*
 ;

mult_expr
 : atom (('*' | '/')^ atom)*
 ;

atom
 : id
 | Num
 | Str
 | '(' expr ')' -> expr
 ;

id
 : Id
 | Include
 ;

Comment  : '!' ~('\r' | '\n')* {skip();};
Space    : (' ' | '\t' | '\r' | '\n')+ {skip();};
If       : 'if';
Include  : 'Include';
Constant : 'Constant';
Id       : ('a'..'z' | 'A'..'Z') ('a'..'z' | 'A'..'Z' | '0'..'9')+;
Str      : '"' ~'"'* '"';
Num      : '0'..'9'+ ('.' '0'..'9'+)?;

main.inf

Constant IMPORT "other.h";

[ Main;
  print "This is Main!";
  if (0) {    

  Include IMPORT;

  print "This is OtherFunction!";
];

другое.ч

  } ! end if
];  ! end Main

[ OtherFunction;

Main.java

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

public class Main {
  public static void main(String[] args) throws Exception {
    // create lexer & parser
    Inform6Lexer lexer = new Inform6Lexer(new ANTLRFileStream("main.inf"));
    Inform6Parser parser = new Inform6Parser(new CommonTokenStream(lexer));

    // print the AST
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT((CommonTree)parser.parse().getTree());
    System.out.println(st);
  }
}

Чтобы запустить демонстрацию, выполните следующие действия в командной строке:

java -cp antlr-3.3.jar org.antlr.Tool Inform6.g 
javac -cp antlr-3.3.jar *.java
java -cp .:antlr-3.3.jar Main

Результат, который вы увидите, соответствует следующему AST:

введите здесь описание изображения

person Bart Kiers    schedule 24.08.2012