Генерация дерева разбора с помощью Java CUP
Я использую CUP с JFlex для проверки синтаксиса выражения. У меня работает базовая функциональность: я могу сказать, является ли выражение допустимым или нет.
Следующим шагом является реализация простых арифметических операций, таких как "добавить 1". Например, если мое выражение "1 + a", результат должен быть "2 + a". Мне нужен доступ к дереву разбора, чтобы сделать это, потому что простое определение числового термина не сделает этого: результат добавления 1 к "(1 + a) * b" должен быть "(1 + a) * b + 1", а не "(2 + a) * b".
У кого-нибудь есть пример CUP, который генерирует дерево разбора? Я думаю, что смогу взять это оттуда.
В качестве дополнительного бонуса, есть ли способ получить список всех токенов в выражении, используя JFlex? Похоже на типичный вариант использования, но я не могу понять, как это сделать.
Редактировать: Обнаружен многообещающий ключ к переполнению стека: создать абстрактное дерево проблем из анализатора
Обсуждение CUP и AST:
http://pages.cs.wisc.edu/~fischer/cs536.s08/lectures/Lecture16.4up.pdf
В частности, этот пункт:
Символ, возвращаемый синтаксическим анализатором, связан с начальным символом грамматики и содержит AST для всей исходной программы.
Это не помогает. Как пройти по дереву данного экземпляра Symbol, если у класса Symbol нет дочерних указателей на его дочерние элементы? Другими словами, он не выглядит и не ведет себя как узел дерева:
package java_cup.runtime;
/**
* Defines the Symbol class, which is used to represent all terminals
* and nonterminals while parsing. The lexer should pass CUP Symbols
* and CUP returns a Symbol.
*
* @version last updated: 7/3/96
* @author Frank Flannery
*/
/* ****************************************************************
Class Symbol
what the parser expects to receive from the lexer.
the token is identified as follows:
sym: the symbol type
parse_state: the parse state.
value: is the lexical value of type Object
left : is the left position in the original input file
right: is the right position in the original input file
******************************************************************/
public class Symbol {
/*******************************
Constructor for l,r values
*******************************/
public Symbol(int id, int l, int r, Object o) {
this(id);
left = l;
right = r;
value = o;
}
/*******************************
Constructor for no l,r values
********************************/
public Symbol(int id, Object o) {
this(id, -1, -1, o);
}
/*****************************
Constructor for no value
***************************/
public Symbol(int id, int l, int r) {
this(id, l, r, null);
}
/***********************************
Constructor for no value or l,r
***********************************/
public Symbol(int sym_num) {
this(sym_num, -1);
left = -1;
right = -1;
value = null;
}
/***********************************
Constructor to give a start state
***********************************/
Symbol(int sym_num, int state)
{
sym = sym_num;
parse_state = state;
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The symbol number of the terminal or non terminal being represented */
public int sym;
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The parse state to be recorded on the parse stack with this symbol.
* This field is for the convenience of the parser and shouldn't be
* modified except by the parser.
*/
public int parse_state;
/** This allows us to catch some errors caused by scanners recycling
* symbols. For the use of the parser only. [CSA, 23-Jul-1999] */
boolean used_by_parser = false;
/*******************************
The data passed to parser
*******************************/
public int left, right;
public Object value;
/*****************************
Printing this token out. (Override for pretty-print).
****************************/
public String toString() { return "#"+sym; }
}
1 ответ
Ладно, я понял. Но, к сожалению, я не могу опубликовать весь свой код здесь как есть. В любом случае я постараюсь наметить решение и, если что-то неясно, задавайте вопросы.
JFlex использует свой собственный Symbol учебный класс. Смотрите здесь:
JFlex.jar/java_cup.runtime/Symbol.class
Вы увидите несколько добавленных конструкторов:
public Symbol(int id, Symbol left, Symbol right, Object o){
this(id,left.left,right.right,o);
}
public Symbol(int id, Symbol left, Symbol right){
this(id,left.left,right.right);
}
Ключ здесь Object o, который является значением Symbol.
Определите свой собственный класс для представления узла дерева AST, а другой - для представления токена лексера. Конечно, вы можете использовать один и тот же класс, но я обнаружил, что более понятно использовать разные классы для различия между ними. И JFlex, и CUP будут генерировать Java-код, и ваши токены и узлы легко перепутать.
Затем в вашем parser.flex в разделах лексических правил вы хотите сделать что-то подобное для каждого токена:
{float_lit} { return symbol(sym.NUMBER, createToken(yytext(), yycolumn)); }
Сделайте это для всех ваших жетонов. Ваш createToken может выглядеть примерно так:
%{
private LexerToken createToken(String val, int start) {
LexerToken tk = new LexerToken(val, start);
addToken(tk);
return tk;
}
}%
Теперь давайте перейдем к parser.cup. Объявите все ваши терминалы, чтобы быть типа LexerTokenи все ваши нетерминалы должны быть типа Node, Вы хотите прочитать руководство CUP, но для быстрого освежения терминалом будет все, что распознается лексером (например, числа, переменные, операторы), а нетерминалом будут части вашей грамматики (например, выражение, коэффициент, термин...).
Наконец, все это объединяется в определении грамматики. Рассмотрим следующий пример:
factor ::= factor:f TIMES:times term:t
{: RESULT = new Node(times.val, f, t, times.start); :}
|
factor:f DIVIDE:div term:t
{: RESULT = new Node(div.val, f, t, div.start); :}
|
term:t
{: RESULT = t; :}
;
Синтаксис factor:f означает, что вы псевдоним фактора значение будет f, и вы можете обратиться к нему в следующем разделе {: ... :}, Помните, что наши терминалы имеют значения типа LexerTokenи наши нетерминалы имеют значения, которые Nodes.
Ваш термин в выражении может иметь следующее определение:
term ::= LPAREN expr:e RPAREN
{: RESULT = new Node(e.val, e.start); :}
|
NUMBER:n
{: RESULT = new Node(n.val, n.start); :}
;
Когда вы успешно сгенерируете код синтаксического анализатора, вы увидите в вашем файле parser.java ту часть, где установлены отношения родитель-потомок между узлами:
case 16: // term ::= UFUN LPAREN expr RPAREN
{
Node RESULT =null;
int ufleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).left;
int ufright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).right;
LexerToken uf = (LexerToken)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-3)).value;
int eleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).left;
int eright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).right;
Node e = (Node)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-1)).value;
RESULT = new Node(uf.val, e, null, uf.start);
CUP$parser$result = parser.getSymbolFactory().newSymbol("term",0, ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)), ((java_cup.runtime.Symbol)CUP$parser$stack.peek()), RESULT);
}
return CUP$parser$result;
Мне жаль, что я не могу опубликовать полный пример кода, но, надеюсь, это сэкономит кому-то несколько часов проб и ошибок. Недостаток полного кода также хорош, потому что он не сделает все эти домашние задания CS бесполезными.
В качестве доказательства жизни, вот симпатичный отпечаток моего образца AST.
Входное выражение:
T21 + 1A / log(max(F1004036, min(a1, a2))) * MIN(1B, 434) -LOG(xyz) - -3.5+10 -.1 + .3 * (1)
В результате АСТ:
|--[+]
|--[-]
| |--[+]
| | |--[-]
| | | |--[-]
| | | | |--[+]
| | | | | |--[T21]
| | | | | |--[*]
| | | | | |--[/]
| | | | | | |--[1A]
| | | | | | |--[LOG]
| | | | | | |--[MAX]
| | | | | | |--[F1004036]
| | | | | | |--[MIN]
| | | | | | |--[A1]
| | | | | | |--[A2]
| | | | | |--[MIN]
| | | | | |--[1B]
| | | | | |--[434]
| | | | |--[LOG]
| | | | |--[XYZ]
| | | |--[-]
| | | |--[3.5]
| | |--[10]
| |--[.1]
|--[*]
|--[.3]
|--[1]
Для генерации деревьев с помощью Cup я использую модифицированную версию Cup, которую вы можете найти по этой ссылке: http://www.skenz.it/compilers/resources/java_cup_v10k_drawTree.zip
Если вы хотите получить больше информации об этом, я предлагаю вам посетить сайт моего преподавателя по части программирования курса Формальные языки и компиляторы в Политехническом университете Турина: http://www.skenz.it/compilers/
Я надеюсь, что это может быть полезно для вас!:)