Можно ли сгенерировать синтаксический анализатор для языка с использованием обратной польской нотации с помощью bison / yacc? - PullRequest
Новая
       1

Можно ли сгенерировать синтаксический анализатор для языка с использованием обратной польской нотации с помощью bison / yacc?

1 голос
/ 24 августа 2010

Можно ли сгенерировать синтаксический анализатор для языка сценариев, который использует нотацию на обратном польском (и синтаксис, похожий на PostScript), используя bison / yacc?

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

/fib
{
  dup dup 1 eq exch 0 eq or not
  {
    dup 1 sub fib
    exch 2 sub fib
    add
  } if
} def

Ответы [ 2 ]

1 голос
/ 24 августа 2010

Учитывая краткое описание выше и заметки в Википедии:
http://en.wikipedia.org/wiki/Stack-oriented_programming_language#PostScript_stacks

Простая грамматика бизонов для вышеперечисленного может быть: 

%token          ADD
%token          DUP
%token          DEF
%token          EQ
%token          EXCH
%token          IF
%token          NOT
%token          OR
%token          SUB
%token          NUMBER
%token          IDENTIFIER

%%


program         :   action_list_opt
action_list_opt :   action_list
                |                           /* No Action */
action_list     :   action
                |   action_list action
action          :   param_list_opt operator
param_list_opt  :   param_list
                |                           /* No Parameters */
param_list      :   param
                |   param_list param
param           :   literal
                |   name
                |   action_block

operator        :   ADD
                |   DUP
                |   DEF
                |   EQ
                |   EXCH
                |   IF
                |   NOT
                |   OR
                |   SUB

literal         :   NUMBER
name            :   '/' IDENTIFIER
action_block    :   '{' program '}'


%%
1 голос
/ 24 августа 2010

Да.Предполагая, что вы имеете в виду тот, который также использует постскриптную нотацию, это означает, что вы бы определили свои выражения примерно так: 

expression: operand operand operator

Вместо более распространенной инфиксной нотации: 

expression: operand operator operand

, но вряд ликвалифицируется как большое дело.Если вы подразумеваете что-то другое под «PostScript-подобным», вам, вероятно, придется уточнить, прежде чем будет дан лучший ответ.

Редактировать: Допустить произвольное количество операндов и операторов также довольно просто: 

operand_list: 
            | operand_list operand
            ;

operator_list: 
             | operator_list operator
             ;

expression: operand_list operator_list
          ;

В данном случае это не попытка принудительно установить нужное количество операторов, присутствующих для какого-либо конкретного операнда - вам придется добавить эти проверки отдельно.В типичном случае постскриптная нотация выполняется на стековом компьютере, поэтому большинство таких проверок становятся простыми проверками стека.

Я должен добавить, что, хотя вы, конечно, можете написать такие парсеры во что-то вродеyacc, языки, использующие нотацию postscript, обычно требуют такого минимального синтаксического анализа, чтобы вы часто передавали их напрямую какому-то интерпретатору виртуальной машины, который выполняет их напрямую, с минимальным синтаксическим анализом (в основном, синтаксический анализ сводится к выдаче ошибки, если вы пытаетесь использоватьимя, которое не было определено).

...