Устранение беспорядочного приоритета в Bison Parser - PullRequest
Новая
       37

Устранение беспорядочного приоритета в Bison Parser

0 голосов
/ 04 мая 2019

В настоящее время я создаю парсер для своего языка, но у меня проблемы с приоритетом (я думаю, что это проблема).Я обнаружил эту проблему только во время создания AST.Я определил следующие токены: 

%token T_SEMICOLON T_COMMA T_PERIOD T_RETURN T_BOOLEAN T_EXTENDS T_TRUE T_FALSE T_IF T_DO T_NEW T_ELSE T_EQUALSSIGN T_PRINT T_INTEGER T_NONE T_WHILE T_NUMBER T_VARIABLE T_LEFTCURLY T_RIGHTCURLY T_LEFTPAREN T_RIGHTPAREN T_ARROW T_EOF

%left T_OR
%left T_AND
%left T_MINUS T_EQUALSWORD T_PLUS 
%left T_GE T_GEQ
%left T_MULTIPLY T_DIVIDE
%right T_NOT

(в данном случае действительно имеют значение только те, которые имеют приоритет), и у меня есть грамматика, которая принимает форму 

Something: T_PRINT expression T_SEMICOLON

, где у меня есть несколько выраженийпроизводств, некоторые из которых 

expression        : expression T_PLUS expression         {$$ = new PlusNode($1, $3);}                             
                  | expression T_MINUS expression        {$$ = new MinusNode($1, $3);} 
                  | expression T_EQUALSWORD expression   {$$ = new EqualNode($1, $3);}          
                  | expression T_MULTIPLY expression     {$$ = new TimesNode($1, $3);}           
                  | expression T_DIVIDE expression       {$$ = new DivideNode($1, $3);} 
                  | T_NOT expression                     {$$ = new NotNode($2);}                               
                  | T_MINUS expression                   {$$ = new NegationNode($2);}                
                  | T_VARIABLE                           {$$ = new VariableNode($1);} 
                  | T_NUMBER               {$$ = new IntegerLiteralNode($1);}                         
                  | T_TRUE                 {$$ = new BooleanLiteralNode(new IntegerNode(1));}                                      
                  | T_FALSE                {$$ = new BooleanLiteralNode(new IntegerNode(0));}                         
                  | T_NEW T_VARIABLE       {$$ = new NewNode($2, NULL);}

, когда я пытаюсь разобрать что-то вроде print true equals new c0 - new c0;, я получаю странный вывод AST, который выглядит как Print(Minus(Equal(BooleanLiteral(1), New("c0")), New("c0"))).Здесь похоже, что токен T_EQUALSWORD имеет более высокий приоритет, чем токен T_MINUS, хотя я определил его иначе?

Эта проблема также возникает, если я заменяю минус на плюс;ввод print true equals new c0 + new c0; Я получаю Print(Equal(BooleanLiteral(1), GreaterEqual(New("c0"), New("c0")))) в качестве вывода.Форма кажется правильной, но я по какой-то причине получаю токен T_GEQ вместо T_PLUS?

Интересно, что вместо этого правильно анализируются T_MULTIPLY и T_DIVIDE:

Ввод: print true equals new c0 * new c0;

Выходные данные: Print(Equal(BooleanLiteral(1), Times(New("c0"), New("c0"))))

Входные данные: print true equals new c0 / new c0;

Выходные данные: Print(Equal(BooleanLiteral(1), Divide(New("c0"), New("c0"))))

Так что, похоже, это работает правильно с умножением и делением, но не работает сплюс и минус.Есть идеи?

РЕДАКТИРОВАТЬ: Я добавил %prec T_OR в производство T_EQUALSWORD, и это решило проблему, когда я использую вычитание, но я все еще получаю странный токен T_GEQ, когда я использую сложение.

1 Ответ

3 голосов
/ 04 мая 2019

Эта строка 

%left T_MINUS T_EQUALSWORD T_PLUS

Означает, что три оператора имеют одинаковый приоритет и связаны слева направо. Первый полученный вами результат соответствует этому. 

a - b - c     (a - b) - c     # Left associative
a - b = c     (a - b) = c     # Also left associative
a = b - c     (a = b) - c     # Once again

Если вы хотите, чтобы равенство было более низким приоритетом, присвойте ему собственный уровень приоритета.

Вторая проблема, связанная с созданием неправильного токена, возможно, связана с тем, что ваш сканер выдает неправильный токен.

...