Re: shunting-yard expression parsing of a JS subset in Python for bytebeat music

Cool.  Here's a small table-driven expression parser in sed,  =

demonstrating that one doesn't need recursion (let alone reasonable  =

control structures or even datatypes other than strings!) to  =

implement* precedence parsing.

As written, it produces human-readable output, but relatively trivial  =

changes to lines [14,18,20,22,24] suffice to output RPN instead:
3+4*5
     54*3+
(P+Q)*R=3DP*R+Q*R;P*(Q+R)=3DP*Q+P*R
     RP*QP*+RQ+P*=3DRQ*RP*+RQP+*=3D;

Right-associative and unary operators would probably each only take  =

one additional substitution rule, but would require additional  =

operator tables.
Precedence groups could probably be implemented with a bit of  =

additional structure for the operator table, requiring changes only  =

in lines [12,14,20].

-Dave

* thank you, Inipocaj-Mh=F6b theorem.

######################################################################## =

########
# simple precedence-climbing parser in sed.
#   parses the following left-associative operators: ; =3D + *
#   right-associative and unary operators left as an exercise for the  =

reader
######################################################################## =

########
# 3+4*5
#     (3+(4*5))
# (P+Q)*R=3DP*R+Q*R;P*(Q+R)=3DP*Q+P*R
#     (((((P+Q))*R)=3D((P*R)+(Q*R)));((P*((Q+R)))=3D((P*Q)+(P*R))))
######################################################################## =

########
# set context
y/abcdefghijklmnopqrstuvwxyz/ABCDEFGHIJKLMNOPQRSTUVWXYZ/;s/.*/&d ;=3D =

+*dd/;:l
# shift parenthesized sub-expression
s/^\((\)\([^d]*\)d\([^d]*\)dd\(.*\)$/\2d =3D+*dd\3b(a\4/;tl
# shift left argument
s/^\(.\)\([^d]*\)d\([^d]*\)dd\(.*\)$/\2d\3d\1d\4/;tl
# shift operator
s/^\(.\)\([^d]*\)d\([^ ]*\) \(.*\)\1\([^d]*\)d\([^d]*\)d\(.*\)$/\2d\3 =

\4\1 \5dd\3 \4\1\5b(\6\1c\7/;tl
# shift right argument
s/^\(.\)\([^d]*\)d[^ ]* .*\1[^d]*d\([^d]*\)d\([^ ]*\) \([^b]*\)b\ =

([^ac]*\)c\(.*\)$/\2d\4 \5d\6\3)d\7/;tl
# reduce sub-expression
s/^)\([^d]*\)d[^d]*d\([^d]*\)d\([^ ]*\) \([^b]*\)b\([^ac]*\)a\(.*\)$/ =

\1d\3 \4d\5\2)d\6/;tl
# reduce term
s/^\([^d]*\)d[^d]*d\([^d]*\)d\([^ ]*\) \([^b]*\)b\([^ac]*\)c\(.*\)$/ =

\1d\3 \4d\5\2)d\6/;tl
# extract return value
s/^.*d.*d\(.*\)d.*$/    \1/

-- =

To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss