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]+


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.

  • 3
    $\begingroup$ Stratego is a system that allows you to write term-rewrite rules and it will compile them for you. $\endgroup$ Nov 21, 2012 at 12:00
  • 1
    $\begingroup$ A link: strategoxt.org $\endgroup$ Nov 21, 2012 at 12:26
  • $\begingroup$ 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? $\endgroup$
    – Dan Gelder
    Nov 21, 2012 at 12:59
  • $\begingroup$ I haven't used it for years, unfortunately. I always mean to, but never find the time. $\endgroup$ Nov 21, 2012 at 15:08
  • $\begingroup$ For actual example using ANTLR see Example tree rewriting with patterns $\endgroup$
    – Guy Coder
    Nov 21, 2012 at 15:34

3 Answers 3


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 :-

% 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) :-


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.