Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Stratego is a system that allows you to write term-rewrite rules and it will compile them for you. – Dave Clarke Nov 21 '12 at 12:00
A link: – Dave Clarke 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? – Dan Gelder Nov 21 '12 at 12:59
I haven't used it for years, unfortunately. I always mean to, but never find the time. – Dave Clarke Nov 21 '12 at 15:08
Correct if I am wrong, but are you thinking in an imperative language? If so,consider using a functional language. – Guy Coder Nov 21 '12 at 15:25

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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