Est-il possible de générer un analyseur pour une langue en utilisant la notation polonaise inversée avec bison/yacc?

Question

Est-il possible de générer un analyseur syntaxique pour un langage de script qui utilise la notation Reverse Polish (et une syntaxe de type Postscript) en utilisant bison/yacc?

L'analyseur doit être capable d'analyser un code similaire à celui qui suit:

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

Answer 1

Compte tenu de la courte description ci-dessus et les notes sur Wikipédia:
http://en.wikipedia.org/wiki/Stack-oriented_programming_language#PostScript_stacks

Un Grammer simple, le bison pour le pourrait être au-dessus:

%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 '}' 


%% 

Answer 2

Oui. En supposant que vous voulez dire celui qui utilise également la notation post-scriptum, cela signifie que vous souhaitez définir vos expressions quelque chose comme:

expression: operand operand operator 

Plutôt que la notation infixe plus commune:

expression: operand operator operand 

mais qui peut difficilement être qualifié d'un grand traiter. Si vous voulez dire autre chose par "Postcript-like", vous devrez probablement clarifier avant de pouvoir donner une meilleure réponse.

Edit: Permettre à un nombre arbitraire d'opérandes et les opérateurs est assez facile:

operand_list: 
      | operand_list operand 
      ; 

operator_list: 
      | operator_list operator 
      ; 

expression: operand_list operator_list 
      ; 

En l'état actuel, cela ne tente pas de faire respecter le bon nombre d'opérateurs étant présents pour tout opérande particulier - vous devrez ajouter ces contrôles séparément. Dans un cas typique, une notation postscript est exécutée sur une machine à pile, de sorte que la plupart de ces vérifications deviennent de simples vérifications de pile.

Je dois ajouter que même si vous certainement pouvez écrire des parseurs quelque chose comme yacc, langues en utilisant la notation postscript nécessitent généralement cette analyse syntaxique minimale que vous les nourrissez souvent directement à une sorte d'interprète de machine virtuelle qui les exécute tout à fait directement, avec une analyse minimale (la plupart du temps, l'analyse revient à lancer une erreur si vous essayez d'utiliser un nom qui n'a pas été défini).