Talk:META II

Just a remark on terminology used below: "META II is a PEG" I think that's not complete. PEG's are parsing languages, a sort of rediscovery of a TDPL or "Top Down Parsing Language" see https://en.wikipedia.org/wiki/Top-down_parsing_language and B. Ford's thesis (he references Birman). Now META II uses an input description which looks a bit like a BNF and could be classified as a (g)TDPL (see original Birman paper and Ford's thesis), or in modern terms as a PEG. However META II is more than just the input description, it is also a compiler which can reproduce itself. Analogous, PEG's are "only" a language description and not an implementation or compiler. So it seems to me there is some confusion as if META II is defined by its input description, or if you also need to take into account its ability to reproduce itself from its input description. — Preceding unsigned comment added by 95.97.91.106 (talk) 12:30, 31 October 2014 (UTC)

I have spent quite a bit of time looking at pegs. And as specified Ford's parsersing expression grammar languages are very simular to Schorre's parser languages ignoring their transformation operators in Schorre's languages.. CWICs "SYNTAX" language is exponentially more powerful then pegs.

Personally I think a better description of Schorre's metalanguages is Parser Programming Language. You are actually coding a recursive decent parser in these languages. I have a real hard time explaining them because of origional research restrictions.

In the META II document the META II compiler source is shown. The first declaration is:

.SYNTAX PROGRAM

And in the PROGRAM declaration we find that a META II program must starts with:

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

A META II program starts with a .SYNTAX declaration specifing a parsing equation that is to be called on startup. That equation is expected to drive the compile. This was one concept of a syntax directed compiler in thoes days.

Typo corrections update.Steamerandy (talk) 20:58, 6 November 2018 (UTC) Steamerandy (talk) 21:38, 17 September 2018 (UTC)

Implementation

I've got an implementation which I'll try to make available at some point. This is based on work done by Kit Lane in around 1987, which was directly based on the Schorre paper. Working language is Pascal. MarkMLl (talk) 10:38, 5 August 2013 (UTC)

META II is a PEG My first contribution

The examples I added shows how META II uses a parsing expression grammar Although the mata II grammar may be more powerful than the parsing language described in the ford document. I have a lot more experience with it's descendants. I wrote a mata compiler that is based on CWIC Compiler for Writing and Implementing Compilers.

CWIC has very powerful lookahead and backtracking. The code generation has been removed from the grammar rules and instead tree and list structures are created by list and tree transform operators in the grammar rules and passed to code generator functions. TREEMETA has tree building and simple code generators called unparse rules. CWIC has the full power of lisp 2 for a generator language. CWIC also maintains a symbol table and functions for converting strings to atomic objects. Atomic objects being numbers, strings etc. All objects are self typed and a variable can contain any type object.

META II used built in function for recognizing symbols and numbers. CWIC had character class and token making rules,

--Steamerandy (talk) 04:45, 1 October 2014 (UTC) (corrected myselfSteamerandy (talk) 19:32, 20 March 2018 (UTC)

Original Paper

Noted that the article links to http://www.hcs64.com/files/pd1-3-schorre.pdf, I notice another copy at http://ibm-1401.info/Meta-II-schorre.pdf which appears to be the same document but possibly scanned by somebody else. I've also got a copy that I transcribed in the 1980s (i.e. it's now a text file rather than a bitmap), but I'm reluctant to upload it anywhere on account of the jealousy with which the ACM guards their archive: they gave me permission at the time but it was in a university teaching context.

I was in touch briefly with Schorre around 10 years ago, he was surprised that anybody was still interested in Meta II. For various reasons I'm reluctant to bother him asking if I can reproduce his paper, i.e. bypassing the ACM altogether. MarkMLl (talk) 08:27, 9 October 2014 (UTC)

Knuth quote

This might be useful at some point, from http://www.bayfronttechnologies.com/mc_tutorial.html

In 1990 when Donald Knuth was asked what helped to crystallize his thinking about attribute grammars he related the following [Knuth90].

   "Many details of those two days (February 4-5, 1967) still remain fresh in my mind. ... Peter [Wegner] asked me what I thought about formal semantics, and I said I liked Iron's idea of synthesizing an overall meaning from submeanings. I also said that I liked the way other people had combined Irons's approach with a top-down or "recursive-descent" parser; Irons had used a more complex parsing scheme. In particular, I was impressed by the metacompiler of Val Schorre [Schorre64] and by the more powerful (though less elegant) "transmogrifier" of Bob McClure [McClure65]."

[Knuth90] D. E. Knuth, "The Genesis of Attribute Grammars," In Proceedings of the International Conference on Attribute Grammars and their Applications (Paris, France). P. Deransart and M. Jourdan, Eds. Springer-Verlag New York, New York, NY, 1-12. 1990.

The "other people" that he referred to were probably Waychoff et al. at Burroughs for whom he consulted, however they rarely published formally so he probably felt it inappropriate to name them. MarkMLl (talk) 11:50, 1 September 2017 (UTC)

Meta derivative at Autodesk Inc

[1] looks like at least a conceptual derivative, it's styled 3.5 with the final digit appearing to be the version or release. I've asked JW whether he can say anything about its provenance. MarkMLl (talk) 10:15, 25 May 2018 (UTC)

Tail Recursion?

Hi Mark. I see you made a change stating that the sequance operator is equilivant to tail recursion. I don't think so. I look at it as equivalent to left recursion. Correct my if I am wrong.

An example in CWICs syntax language using tree transform operators.

dgt: '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
lwr: 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'
    |'k'|'l'|'m'|'n'|'o'|'p'|'q'|'r'|'s'|'t'
    |'u'|'v'|'w'|'x'|'y'|'z';
upr:|'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'
    |'K'|'L'|'M'|'N'|'O'|'P'|'Q'|'R'|'S'|'T'
    |'U'|'V'|'W'|'X'|'Y'|'Z';
let:      upr|lwr;
alphanum: let|dgt;

id .. let $(alphanum|+'_');
number .. dgt $dgt MAKENUM[];

expr = term $(('+':ADD|'-':SUB)term!2);
term = factor $(('*':MPY|'/':DIV)factor!2);
factor = ('(' expr ')' | id | number)
         ('^' factor:EXP!2|,EMPTY);

The $ zero or more sequance operator loops until its operand returns failure. Note that in factor I do use what I think is right or tail recursion. At least that is how I have understood the term for the last 52+ years. I admit I could be wrong. A lot of things have changed over the years. But no matter. What is important is the left recursion replacing loops produce a left handed tree and right recursion produces right handed trees.

The rules above parsing 2*a^x^2*c+3*x generates the following tree:

           ADD
          /   \
       MPY     MPY
      /   \   /   \
   MPY     c 3     x
  /   \
 2     EXP
      /   \
     a     EXP
          /   \
         x     2

Left recursion implies a left derivation while right recursive implies a right derivation. I do not like the term derivation because of how it is commonly explained as following a tree. We are programming the building of the tree.

I think the thing is that using a sequance operator you get an LL parse expresion while using right recursion makes it an LR parse expression.

TREEMETA's [<number>] is equivalent to CWIC's !<number> operation.

I think that CS termonolgy changing over the years has caused most of the misunderstanding of these old systems. In the 1960s Chomsky's ideas hadn't infected CS. Actually I like Chomsky. Bur I think the best technology for compiler devopment was these old compiler compilers. Steamerandy (talk) 08:39, 17 September 2018 (UTC)

@Steamerandy

From above (Cleaned and formated for readability:

expr = term $(('+':ADD|'-':SUB)term!2);

term = factor $(('*':MPY|'/':DIV)factor!2);

factor = ('(' expr ')' | id | number)

('^' factor:EXP!2| .EMPTY);

The rules above parsing:

2*a^x^2*c+3*x

generates them following tree:

ADD

/ \

MPY MPY

/ \ / \

MPY c 3 x

/ \

2 EXP

/ \

a EXP

/ \

x 2

In the above the $ sequence looping operator generates a left descending tree. Recursion produces a right descending tree.

I'm steamerandy. Lost my id etc in a recent house fire. 216.146.244.139 (talk) 03:20, 21 April 2023 (UTC)

Declaritive or impariative?

I think it is important to note that META II is an impariative language in declaritive clothing. So to speak. That is it is a programming language having symantec's very specifically defining the order of execution and operations performed. Thoes specifications define the order of execution within a rule to be down line by line and with in a line to be left to right. Alternatives are also atempted in a like manner. Parenthesized expressions are treated as unnamed sub-rules. These are stack based string orianted languages. Tokens are pushed onto the parse stack. They are poped and output by a * argument in a .OUT call. Looking at the examples in the META II document we see in the examples that on recognizing a number .OUT('LDL ' *) outputs LDL followed by the recignized literal poped by the * parameters. .OUT('LD' *) follows the .ID test. META II was as stated a proof of concept. It generally is only capable of producing code for stack machine architectures.

These stack machines were generally interpretive software implementations.

Old post above I'm confident was by me. Steamerandy (talk) 21:15, 6 November 2018 (UTC)

Exponentiation operator in example looks wrong

Modification of 23:59, 13 September 2018‎ introduced ^ as the exponentiation operator in the rule for "factor"... that doesn't look right to me. If somebody's got the original working rules that that was taken from please could they check: it's definitely not in Schorre's paper. MarkMLl (talk) 18:36, 6 October 2021 (UTC)

Hi Mark. You are right. I added exponaton to show how tall recursion creates a right descending tree. 209.152.148.114 (talk) 15:20, 25 July 2024 (UTC)