Talk:History of compiler construction

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Untitled[edit]

This article comes from an outgrown history section in the article Compiler along with older references. There appears to be enough material to create a good article although it definitely needs some work. See also [1]. pgr94 (talk) 13:30, 29 January 2009 (UTC)

I'd agree that such an article is academically useful, although, I might add, some might belong in the Compiler article proper as still technically relevant, fostering understanding with seminal concepts. --- (Bob) Wikiklrsc (talk) 15:18, 29 January 2009 (UTC)

This deserves to be an article in its own right. Do not merge with Compiler or Compiler construction.Paul Foxworthy (talk) 12:10, 30 June 2011 (UTC)

I'm interested in this sentence: "LR parsing can handle a larger range of languages than LL parsing, and is also better at error reporting" because from what I've learned, known, and experienced, LR parsing cannot detect exact error location because the reduce step could have more than one possibilities. It can only be "somewhere around here". Should it be corrected? Or if anyone has a proof, please tell me. Leledumbo (talk) 16:23, 08 December 2011 (UTC + 7)

Hi Leledumbo, the LR parser article states

LR parsing can handle a larger range of languages than LL parsing, and is also better at error reporting, i.e. it detects syntactic errors when the input does not conform to the grammar as soon as possible. This is in contrast to an LL(k) (or even worse, an LL(*) parser) which may defer error detection to a different branch of the grammar due to backtracking, often making errors harder to localize across disjunctions with long common prefixes.

No source cited, but I hope that helps. Paul Foxworthy (talk) 13:07, 11 March 2012 (UTC)

I thought that's where this article takes the sentence from, that's why the sentence is exactly the same. Anyway, from papers I read, each author says different things depending the method he/she prefers to use, and I never one that really speaks the fact about both methods from neutral point of view. --Leledumbo (talk) 05:53, 12 March 2012 (UTC)

Direct quotation of a paragraph?[edit]

The paragraph on Frances Allen appears to be a direct quotation from her Turing award citation. Should this be sourced differently? 108.36.110.176 (talk) 12:06, 21 June 2013 (UTC)

Link no longer exists[edit]

This reference contains a link to a page at the Computer History Museum that no longer exists.

<ref name="computerhistory.org">[http://www.computerhistory.org/events/lectures/cobol_06121997/index.shtml] The World's First COBOL Compilers</ref>

RussAbbott (talk) 20:52, 30 June 2013 (UTC)

Inconsistency[edit]

"Any program written in a high level programming language must be translated to object code before it can be executed" Is inconsistent with actions performed by some interpreters. Interpreters must perform similar code analysis. But translation to object code is not necessarily the result.

--Steamerandy (talk) 17:30, 27 October 2014 (UTC)

The first self-hosting compiler appears to be the NELIAC ALGOL compiler in 1958. Not LISP in 62. Steamerandy (talk) 07:11, 3 January 2015 (UTC)


BNF was not used in the specification of ALGOL 58. It was first used in the specification of ALGOL 60

Steamerandy (talk) 22:56, 24 March 2015 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just added archive links to one external link on History of compiler construction. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

YesY An editor has reviewed this edit and fixed any errors that were found.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—cyberbot IITalk to my owner:Online 22:20, 26 January 2016 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified one external link on History of compiler construction. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

YesY An editor has reviewed this edit and fixed any errors that were found.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 10:18, 3 April 2017 (UTC)

Grammar description languages[edit]

META II and other META "languages" based on Dewey Val Shorre's transformational metalanguages are in part grammar description languages. That would also includes TREE-META and CWIC. Dewey was a member of the CWIC development team.

These grammar description languages are best described as parser programming languages. They are top-down or reductive analytical grammars. It would be hard to improve on CWIC's SYNTAX (parser programming language). I implemented SLIC based on CWIC and only made two changes to the SYNTAX language neither of which effected its parsing capabilities.

In these languages you program a top-down reductive analyses. Basically a recursive decent parser. CWIC and SLIC compiled to machine code creating fast efficient compilers. SLIC was used to write a COBOL cross-compiler. It implemented exactly the DEC-10 COBOL syntax. Having the same RECORD CONTAINS bug as DEC's. The COBOL compiler was completed taking only 3 man-months. It compiled more lines/sec then the supplied DEC-10 COBOL compiler.

A example is worth more then words:

 expr=term $(('+':ADD|'-':SUB) term!2);
 term = factor $(("*':MPY|'/':DIV) factor!2);
 factor = (id | number | '(' expe ')' )( '^' factor:POW!2|.EMPTY);
Token formula:
 id .. let $(alphanum|+'_');
 number .. dgt $dgt MAKENUM[];

The above set of parser formulae produce a left or right handed syntax tree appropriate to the operation. +,-,*,/ left handed and ^ right handed. The $ zero or more loop operator is equivalent to the * used today in regular expressions. The expr:

 2*x^3-3*(t^2+5)-8

parsed by the above formulae would be transformed into a tree:

 SUB[SUB[MPY[12,POW[x,3]],MPY[3,ADD[POW[t,2],5]]],8]

            SUB
           /   \
        SUB     8
       /   \
    MPY     MPY
   /   \   /   \
 12   POW 3     ADD
     /   \     /   \
    x     3  POW    5
            /   \
           t     2

The tree is constructed on the parse stack. Token formula recognize token strings creating token objects that are pushed in the parse stack.. By default a recognized token is cataloged into the dictionary creating a symbol object. There are supplied interceding functions the create numeric and string objects bypassing cataloging. The :<id> operation. rates a node object and pushes it on the node stack. !<number> pops the top number of parse stack entries and top node stack object in to a list. The list then pushed on the parse stack. The stack tree construction is a global system allowing tree construction independent of the formula allowing factoring that eliminates backtracking. Formula are test functions. A test being an action returning success or failure. On success the parse has advanced. On failure the parse state is unchanged. Test can be thought of a boolean type: success=true and failure=false. A formula is a test function. Test also being an action are performed in left to right order and down. A test may long fail by passing stacked formula formule. The backtrack alternative \ sets a backtrack point ahead of its left alternative. A backtrack is liken to a longjump in c. Only the parse state was save and on a failure return the parse state restored:

program = $( ( declaration                        // A program is a sequance of
                          | .EOF .STOP)                      // declarations terminated by
                                                                       // End Of File or on an error
                        \ ERRORX["Error"]                // backtrack and report error
                                                                       // flaging furthest parse point.
                          $(-';' (.ANY|.EOF .STOP))  // Error recovery find a ; or
                                                                      // terminate on an EOF. On matching
                           ';');                                      // a ; continue the declaration loop

The above program formule defines a program to be a sequence of declaration that is terminated by End of File .EOF

But includes error reporting and recovery.

You can find a short paper on CWIC in the ACM archive.

SLIC'S SYNTAX and GENERATOR were basically the same as CWIC's. Only the generator language was changed to produce PSEUDO instructions appending them to section lists. CWIC produced 8, 16 and 32 bit value into memory blocks associated with named sections. Code write by a

.FLUSH <section name>

SLIC added PSEUDO and MACHOP defining languages. PSEUDO procedures were coded in LISP 2 dialect simular to GENERSTOR actions. MACHOP are also procedurally defined output functiond. MACHOPs are use to define a target machines instructions. The define an instruction or family of like formated instruction as a sequence of bit fields. Conditional expressions are used in selecting different sequences or field values. The also specify assembly listing formating that optionally can be output to the compile listing. A helpful compiler debugging aid.

I am interested in deturmining the grammar type. Reductive is not recognized today. CWIC should be in this history. But as it is it doesn't fit. These were called metacompilers. All Shorre based metacompilers work in simular manor. META II had a *stack that in the output productions were pope and output by a *1 argument. CWIC used a *1 argument in generator calls from a syntax formuls to pop the top parse stack entry. .ID, .NUMBER, and .STRING were built in token recognizing functions in parser languages previous to CWIC. Steamerandy (talk) 23:06, 31 October 2017 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on History of compiler construction. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 02:06, 5 November 2017 (UTC)