Is it possible to generate a parser for a language using the Reverse Polish notation with bison/yacc?

Question

Is it possible to generate a parser for a scripting language that uses the Reverse Polish notation (and a Postscript-like syntax) using bison/yacc?

The parser should be able to parse code like

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

Answer 1

Yes. Assuming you mean one that also uses postscript notation, it means you'd define your expressions something like:

expression: operand operand operator

Rather than the more common infix notation:

expression: operand operator operand

but that hardly qualifies as a big deal. If you mean something else by "Postcript-like", you'll probably have to clarify before a better answer can be given.

Edit: Allowing an arbitrary number of operands and operators is also pretty easy:

operand_list: 
            | operand_list operand
            ;

operator_list: 
             | operator_list operator
             ;

expression: operand_list operator_list
          ;

As it stands, this doesn't attempt to enforce the proper number of operators being present for any particular operand -- you'd have to add those checks separately. In a typical case, a postscript notation is executed on a stack machine, so most such checks become simple stack checks.

I should add that although you certainly can write such parsers in something like yacc, languages using postscript notation generally require such minimal parsing that you frequently feed them directly to some sort of virtual machine interpreter that executes them quite directly, with minimal parsing (mostly, the parsing comes down to throwing an error if you attempt to use a name that hasn't been defined).

Answer 2

Given the short description above and the notes on Wikipedia:
http://en.wikipedia.org/wiki/Stack-oriented_programming_language#PostScript_stacks

A simple bison grammer for the above could be:

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


%%