Re: parsing, PEG parsers, and backtracking HTML templating: toward a bright parsing future (examples in OCaml, C++, and Ruby)

> (which itself refers to Schorre, D.V. "META II: A Syntax-Oriented  
> Compiler Writing Language". Proc. 19'th Nat'l. Conf. of the ACM  
> (Aug. 1964) [1])

According to Alan Kay, META II ran on an 8k 1401[0].

I was able to bootstrap it using the same technique as for your  
quasiquote DSL, composing the following two steps:
	- parse (list of tokens -> tree), unfolding with an operator  
precedence parser:
		binary ops: ., = /  (none right-associative)
		unary ops: $ .OUT
	- codegen (tree -> list of characters) via a bottom-fold
		(plus a one-off kludge to handle the .SYNTAX progname ... .END  
wrapping)
In other words, the same basic computation as factorial, just with a  
few more fiddly details...

Conjecture: given general mixfix ops, can any well-formed LL(1) text  
be processed by a precedence-climbing parser? (False; exercise: find  
the counterexample)

With Schorre's META II VM also coded, his original syntax-directed  
translator[1] self-reproduces.
Furthermore, with a slightly modified grammar spec[2], META II can  
produce a python translator from META II code, self-reproduce the  
python translator, then reproduce a META II translator from the  
original grammar.

Note that Schorre had tight memory limits, and hence META II normally  
streams all data (would aggressive deforestation be "clearcutting"?),  
reading input a card at a time and punching output similarly.  Today,  
we have scratch space to burn; given a .EDIT that could (a la sed)  
prepend material to the previous production as well as the  
existing .OUT which simply appends, one could simplify the grammar  
and avoid gratuitous use of monoid identities ('True' and '' for  
juxtaposition and output). (cf TREE-META)

Anyhow, the pleasant result that LL parsers are quickly implementable  
from simple operator precedence seems to give a relatively smooth  
bootstrap path:
	- hex loader
	- symbol table & stack (roughly a minimal FORTH[-1])
	- operator precedence parser (alternatively, ignore precedence but  
support juxtaposed literals to get a minimal APL)
	- meta-ii style translator (should handle a minimal PASCAL/MODULA/ 
OBERON or K&R C; cf VALGOL,tcc)
	- ...

-Dave

[-1] it's not exactly bare metal, and probably much more complicated  
than a forth dictionary, but it might be a neat hack to cheat on a  
laptop by using the existing dynamic linker (dlopen/dlsym or  
equivalent) for this step...
[0] which was a six-bit machine, explaining the use of '.,' instead  
of ';', so should we say 6k for modern comparisons?
[1]
.SYNTAX PROGRAM

OUT1 = '#1' .OUT('GN1') / '#2' .OUT('GN2') /
'#' .OUT ('CI') / .STRING .OUT('CL ' #).,

OUTPUT = ('.OUT' '('
$ OUT1 ')' / '.LABEL' .OUT ('LB') OUT1) .OUT('OUT').,

EX3 = .ID .OUT ('CLL' #) / .STRING
.OUT('TST' #) / '.ID' .OUT('ID') /
'.NUMBER' .OUT('NUM') /
'.STRING' .OUT('SR') / '(' EX1 ')' /
'.EMPTY' .OUT('SET') /
'$' .LABEL #1 EX3
.OUT ('BT ' #1) .OUT('SET').,

EX2 = (EX3 .OUT('BF ' #1) / OUTPUT)
$(EX3 .OUT('BE') / OUTPUT)
.LABEL #1 .,

EX1 = EX2 $('/' .OUT('BT' #1) EX2 )
.LABEL #1 .,

ST = .ID .LABEL # '=' EX1
'.,' .OUT('R').,

PROGRAM = '.SYNTAX' .ID .OUT ('ADR' #)
$ ST '.END' .OUT ('END').,

.END

[2]
.SYNTAX PROGRAM

OUT1 =	'#1'	.OUT('1,') /
	'#2'	.OUT('2,') /
	'#'	.OUT('0,') /
	.STRING	.OUT(# ',').,

OUTPUT = ('.OUT' .OUT('out(') '(' $ OUT1 ')' /
	'.LABEL' .OUT('label(') OUT1 ) .OUT('"")').,

EX3 =	.ID	.OUT (# '()') /
	.STRING	.OUT('lit(' # ')') /
	'.ID'	.OUT('id()') /
	'.NUMBER' .OUT('num()') /
	'.STRING' .OUT('string()') /
	'(' .OUT('(') EX1 ')' .OUT(')') /
	'.EMPTY' .OUT('True') /
	'$'	.OUT('loop(lambda:(') EX3 .OUT('))').,

EX25 = (EX3 / OUTPUT) .OUT('and').,

EX2 =	EX25 $ EX25 .OUT('True').,

EX1 =	EX2 $('/' .OUT('or') EX2 ).,

ST =	.ID .OUT(# '=lambda:gnstack(lambda:(') '=' EX1 '.,' .OUT('))') .,

PROGRAM =		.LABEL 'from mplib import *'
			.LABEL 'if True:'
	'.SYNTAX' .ID	.OUT ('main=lambda:' # '()')
	$ ST '.END'	.OUT('if __name__=="__main__": main()') .,

.END

-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss