правило максимального жаворонка с yacc / bison - кажется, что берут минимальное жавление - PullRequest
Новая
       47

правило максимального жаворонка с yacc / bison - кажется, что берут минимальное жавление

0 голосов
/ 30 апреля 2020

Я пытаюсь ввести новую языковую конструкцию в большую / сложную грамматику. Я знаю, что это сделает синтаксис неоднозначным, но я надеюсь разрешить это с помощью правила «максимальное жаворонок». То есть сначала поставьте мою конструкцию, чтобы она воспринималась по предпочтению. У меня есть некоторый успех, но других частей дерева не так много. Подумайте: 

( 1, 2, 3 )          // triple
( 4, 5 )             // twople
( 6 )                // *not* a oneple, see below
()                   // zerople

(7 + 8) * 9          // single parens used to override usual precedence
( (( 7 + 8 )) * 9 )  // currently this means the same, but nobody would write that!

(( 6 ))              // I want to be a oneple
( ( 6 ) )            // this also a oneple
( ( ( 6 ) ) )        // this also a oneple with a superfluous pair of parens, ambiguous
((  ( 6 )  ))        // superflous parens are innermost
(  (( 6 ))  )        // superfluous parens are outermost

((7 + 8) * (9 + 10)) // not a oneple, despite the (( ... ))

Эти три примера с 6 в трех парах паренсов неоднозначны, меня не волнует, какая из них занимает грамматика, они семантически одинаковы. По правилу «максимального жаворонка» он должен принимать середину трех, то есть оставлять самые внутренние паренны за лишние.

Лексер принимает каждый (, ) в качестве отдельного токена. В настоящее время синтаксический анализатор принимает ( ( ( 6 ) ) ) как эквивалент 6 (где он анализируется как expr / int) - то есть то, что сделала грамматика прежде чем я попытался изменить его.

Грамматика имеет много уровней токенов, определенных другими токенами. Некоторые выражения в некоторых контекстах распознают двойные скобки ОК. Других не так много (и это трудно свести к примеру разумного размера). Существуют ли какие-либо общие приемы, позволяющие уговорить бизонов на максимальный вкус?

Addit: Эта неоднозначность аналогична известной неоднозначности на самом первом языке использования BNF: ALGOL 60 

if cond1    then 
  if cond2  then blah2
 else            blah3;      // is this on cond2 False or cond1 False?

Это было решено, сказав, что else присоединяется к самому внутреннему if/then, который еще не получил else, то есть к cond2 False в этом случае; оставляя cond1 без else ветви. (У Алгола не было «правила офсайда», слава богу!)

Addit2: ОК, по многочисленным просьбам код ya cc до того, как я начал вносить поправки, равен здесь (Теперь вы собираетесь wi sh, который вы никогда не спрашивали.) Это, например, работает в правиле aexp (средняя строка - мой мод) 

  | '(' exp ')'         {$$ = gc3($2);}
  | '(' '(' exp ')' ')'     {$$ = gc5(buildTuple(cons($3,NIL)));}   /* ADC Apr-2020  */
  | '(' exps2 ')'       {$$ = gc3(buildTuple($2));}

Эта строка не работает - в правиле apat pat продолжает анализироваться как обычный шаблон с несколькими скобками. 

apat      : NUMLIT          {$$ = $1;}
  | var             {$$ = $1;}
  | '(' '(' pat ')' ')'     {$$ = gc5(buildTuple(singleton($3)));}  /* ADC Apr-2020 */
  | apat_vI         {$$ = $1;}
  ;

Я попытался вставить эту строку во все виды мест вверх и вниз по дереву из pat; Я даже пытался поставить его в нескольких постановках одновременно, что выглядит довольно хитро. Парсер, похоже, постоянно игнорирует это.

Спасибо за ответ @Chris Dodd. Я думал, что, несмотря на это, приводя к ошибкам сдвига / уменьшения, я читал в других SO-ответах, что бизон «делает правильные вещи» - то есть, если вы поставите одно произведение выше другого, оно предпочтет это сначала.

Ответы [ 2 ]

0 голосов
/ 30 апреля 2020

Я исправил это; это не имеет ничего общего с приоритетом %left / %right.

Обратите внимание, что в Addit2: работающем коде есть один и тот же нетерминальный pat, появляющийся в двух правилах, которые потенциально неоднозначны; и терминалы, которые их дифференцируют, также появляются (одиночная пара против удвоенной пары). Принимая во внимание, что в примере проблемного c «конкурирующие» нетерминалы называются по-разному; и нет терминалов.

В этих правилах для apat, NUMLIT не может начинаться с (, как и var. apat_vI может начинаться с (, поэтому переместите это правило для pat в него. (Посмотрите репо, с которым я связан, если вы следуете дома.)

Но недостаточно просто перенести правило в apat_vI. Вот несколько критических строк: 

  | '(' pat_npk ')'     {$$ = gc3($2);}   
  | '(' npk ')'         {$$ = gc3($2);}                  
/*    | '(' '(' pat ')' ')'     {$$ = gc5(buildTuple(singleton($3)));}      /*   ignored */
  | '(' '(' pat_npk ')' ')'     {$$ = gc5(buildTuple(singleton($3)));}  /* same non-term */

Закомментированная строка с pat - это та, которую я переместил, но она не устраняет двусмысленность. (И не уменьшает количество конфликтов сдвига / уменьшения.)

Глядя на произведения с pat, они npk или pat_npk. В этом случае npk не может начинаться с ( - поэтому игнорируйте его; pat_npk может. Поэтому измените pat на pat_npk, и это уменьшит конфликты сдвига / уменьшения на 2.

( ( ( 6 ) ) ) теперь анализируется так же, как (( 6 )), в отличие от голого 6. Вот сеанс с использованием языка: 

Main> let foo x = (( x )) in foo 6           -- (( x )) in exp always worked
(( 6 ))
Main> let bar (( x )) = x in bar (( 6 ))     -- (( x )) in pat got treated as bare x
6
Main> let bar (( x )) = x in bar (( (6) ))   -- three pairs of parens treated as a double
6
Main> let bar (( x )) = x in bar (( ((6)) )) -- four pairs of parens treated as two doubles
(( 6 ))

Критические характеристики c:

  • Зубр должен быть в состоянии видеть, что в правилах для apat_vI есть два производства, которые включить же нетерминал pat_npk; и
  • , что их контекст отличается терминалами (пара паренов против удвоения).
  • Затем при встрече ( во входящей строке токена, парсер будет сдвигаться и ждать, чтобы узнать, получит ли он другой.

Так же, как в конфликте if / else: побудить парсер сдвинуть первый else и подождать, чтобы увидеть, получит ли он другой.

0 голосов
/ 30 апреля 2020

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

%token NUM NAME
%left '+' '-'
%left '*' '/'
%nonassoc PREFIX
%%

expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | '-' expr %prec PREFIX
    | '(' expr ')'   /* parentheses for grouping */
    | NUM
    | NAME
    | '(' exprlist ',' expr ')' /* tuple */
    | '(' '(' expr ')' ')'      /* one-ple */
    ;

exprlist: expr | exprlist ',' expr ;

Эта грамматика неоднозначна и имеет один конфликт сдвига / уменьшения, вытекающий из этого. Но стандартное разрешение предпочитать-сдвиг-над-уменьшением приведет к его синтаксическому анализу с правилом «one-ple» вместо правила «скобок» дважды.

Однако, если вы добавите директиву %left ')', это разрешит это противоположным способом (и сообщит о «правиле, бесполезном из-за конфликтов» для правила «один-единственный»)

...