# thue2sed - converts a Thue program to sed
# (C) 2003 Laurent Vogel 
# GPL version 2 or later (http://www.gnu.org/copyleft/gpl.html)
#
# Thue info at: http://www.catseye.mb.ca/esoteric/thue/

# notes
# - Due to the way sed handles input, the resulting program will skip
#   the first input line: when running the resulting program, one must 
#   supply this first input line, which will always be ignored.
# - the rules are triggered in deterministic order: they are tried one 
#   after the other in a big loop.
# - implements modified Thue where foo::=~bar does only output a newline
#   when bar is empty.
# - This should be absolutely portable sed. Please tell me if it is not.
#
# options
# - debug output - print the pattern space after each change
# - verbatim comments - lines starting with # passed verbatim
# - original output - newline printed at each output rule
# (These options can be activated by commenting/uncommenting
# unique lines. Each such lines has the comment OPTION above it)

# Consider line number in hold buffer
x

# OPTION
# To activate debug output, uncomment this line: 
# the Thue pattern space will be printed after each replacement.
# 1s/^/D/

# In second phase, emit code to accumulate to the data space
/^S/{
  x
  $a\
b loop
  /./{
    # quote metacharacters
    s/[\/&]/\\&/g
    s/.*/s\/$\/&\//
    p
  }
  d
}

# Initialize the line number
1s/$/0/

# Increment line number
s/$/+012345678910999000990090/
s/\(.\)\(9*\)+[^9]*\1\(.0*\).*\2\(0*\).*/\3\4/

# Emit the prologue. The data space will be set up by :init at the end.
1i\
# generated from thue by thue2sed\
b init\
:loop

# debug? 
/^D1$/i\
t out\
:out\
p

# Back to thue source code
x

# OPTION
# To pass lines starting with # as sed comments, uncomment next line
/^#/b verbatim

# Pass empty lines untouched
/^$/{
  :verbatim
  s/^#::=/#/
  p
  d
}

# If there is no `::=', it is an error. Report it by creating a sed
# program that quits immediately after printing the error message.
/::=/!{
  :error
  # quote sed metacharacters
  s/[/\&]/\\&/g
  # get the line number from the hold buffer
  G
  s/\(.*\)\nD*\(.*\)/:init\
i\\\
Syntax error line \2:\
s\/.*\/\1\/\
q/
  q
}

# Handle the two cases where ::= is at the beginning of the line.
# Any other cases are valid rules, handled below.
/^::=./b error
/^::=$/b init

# We now proceed to quote the sed metacharacters differently in the
# left and right part of the rule. First, replace the first ::= by \n
s/::=/\
/
# Quote sed meta characters for the left part of rules
H
s/\n.*//
s/[.*$^\/[]/\\&/g
# Quote sed meta-characters for the right part of rules
x
s/\(\n\).*\n/\1/
s/[\/&]/\\&/g
# Assemble back the line number, left and right parts:
# the hold buffer should contain only the line number; 
# the pattern space will contain <left>\n:<right>
H
s/\n.*//
x
s/\(\n\).*\n/\1:/

# Common code for output patterns:
s/\(.*\)\(\n\):~/\/\1\/{\2  s\/\/\/\2~/

# OPTION
# To implement the original Thue output behaviour (one newline after
# each output rule), uncomment the next line.
# s/\(\n\)~\(.*\)/\1  x\1  s\/^\/\2\/p\1  s\/.*\/\/\1  x\1}/

# Newline output pattern
s/\(\n\)~$/\1  x\1  p\1  s\/.*\/\/\1  x\1}/

# Other output pattern
s/\(\n\)~\(.*\)/\1  x\1  s\/$\/\2\/\1  x\1}/

# Input pattern
s/\(..*\)\(\n\)::::$/\/\1\/{\2  N\2  s\/\1\\(.*\\)\\n\\(.*\\)\/\\2\\1\/\2}/

# Replacement pattern
s/\(..*\)\n:\(.*\)/s\/\1\/\2\/g/

# Print the code handling this pattern 
p
  
# Debug?
x
/^D/i\
t out
x

# Done for this line
d 

:init

# We now write the code initialising the pattern space
# code inserted: 
# - at the end of loop: loop if a rule matched; print leftover output; quit
# - at init: delete first input line.
i\
t loop\
x\
q\
:init\
g

# enter the second phase
x
s/^/S/
x
d