# Example of a parsing/rewriting system?

I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually implemented examples of rewriters. For example, suppose I had the rules

WORD: [A-Z]+

QUOTE: "

And I wanted to input a lot of words,put quotes around each one, and write out the string. Or go back and forth. Something like this:

(WORD [' '])+ <--> (QUOTE WORD QUOTE [' '])+

That seems kind of possible to implement automatically without ambiguity, but I was hoping someone had seen something along that line that already exists.

• Stratego is a system that allows you to write term-rewrite rules and it will compile them for you. Nov 21 '12 at 12:00
• A link: strategoxt.org Nov 21 '12 at 12:26
• Hi @Dave. I read up on it and it's pretty complex. Do you use it for anything? Can you describe the syntax for the above example? Nov 21 '12 at 12:59
• I haven't used it for years, unfortunately. I always mean to, but never find the time. Nov 21 '12 at 15:08
• For actual example using ANTLR see Example tree rewriting with patterns Nov 21 '12 at 15:34

Thue language is based on string rewriting and it's just 179 lines of c code.

Pure is an LGPL'd functional language based on term rewriting.

Not an example, but a course with really complete slides on the theory of term rewriting systems.

My DMS Software Reengineering Toolkit is an example of a system based on rewriting terms (ASTs produced by parsing), used to carry out massive code transformations. You can see a description of its rewrite rules.

I wrote a relatively simple bottom-up parser using a string rewriting system in Prolog. In this example, the input is [a,plus,b,plus,sum,of,c,and,d] and the output is [[[a,+,b],+,c],+,d]:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
rewrite_system([a,plus,b,plus,sum,of,c,and,d],X),writeln(X).

% this predicate is from https://stackoverflow.com/a/8312742/975097
replace(ToReplace, ToInsert, List, Result) :-
once(append([Left, ToReplace, Right], List)),
append([Left, ToInsert, Right], Result).

rewrite_system(Input,Output) :-
is_terminal(Input),Input=Output;
rewrite_rule(A,B),
replace(A,B,Input,Input1),
writeln(Input1),
rewrite_system(Input1,Output).

rewrite_rule([sum,of,A,and,B],[A,plus,B]).
rewrite_rule([A,plus,B],[A,+,B]).
rewrite_rule([A,+,B],[[A,+,B]]).
is_terminal([A,+,B]).


Using the same principle, I wrote an adaptive parser that "learns" new grammar rules from its input.