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=P*R+Q*R;P*(Q+R)=P*Q+P*R
RP*QP*+RQ+P*=RQ*RP*+RQP+*=;
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öb theorem.
########################################################################
########
# simple precedence-climbing parser in sed.
# parses the following left-associative operators: ; = + *
# right-associative and unary operators left as an exercise for the
reader
########################################################################
########
# 3+4*5
# (3+(4*5))
# (P+Q)*R=P*R+Q*R;P*(Q+R)=P*Q+P*R
# (((((P+Q))*R)=((P*R)+(Q*R)));((P*((Q+R)))=((P*Q)+(P*R))))
########################################################################
########
# set context
y/abcdefghijklmnopqrstuvwxyz/ABCDEFGHIJKLMNOPQRSTUVWXYZ/;s/.*/&d ;=
+*dd/;:l
# shift parenthesized sub-expression
s/^\((\)\([^d]*\)d\([^d]*\)dd\(.*\)$/\2d =+*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
