Misplaced Pages

#605394

27-427: XPL was designed and implemented by William M. McKeeman , David B. Wortman , James J. Horning and others at Stanford University . XPL was first announced at the 1968 Fall Joint Computer Conference . The methods and compiler are described in detail in the 1971 textbook A Compiler Generator . They called the combined work a 'compiler generator'. But that implies little or no language- or target-specific programming

54-639: A bottom-up parsing method, in which the compiler can delay its decision about which syntax rule it has encountered until it has seen the rightmost end of that phrase. This handles a wider range of programming languages than top-down methods, in which the compiler must guess or commit to a specific syntax rule early, when it has only seen the left end of a phrase. XPL includes a minimal runtime support library for allocating and garbage-collecting XPL string values. The source code for this library must be included into most every program written in XPL. The last piece of

81-486: A "loader" for XCOM itself or any programs which were developed using XCOM, and also provides three auxiliary storage devices for XCOM's use, and which are directly accessed by block number. The originally published XMON was optimized for IBM 2311s . An XMON parameter FILE= enabled the monitor to efficiently use other disks with larger block sizes. The working disk block size was also a compile-time constant in XCOM. XMON used

108-506: A now-obsolete bottom-up parse table method called Mixed Strategy Precedence , invented by the XPL team (although the officially released version retains the MSP parser and does not include later-released "peephole optimizations" and additional data types which were developed outside of the original implementation team.) MSP is a generalization of the simple precedence parser method invented by Niklaus Wirth for PL360 . Simple precedence

135-443: A number of compilers for various languages and systems. XPL continues to be ported to current computers. An x86/ FreeBSD port was done in 2000, an x86/ Linux port in 2015, and an XPL to C translator in 2017. Jim Horning James Jay Horning (August 24, 1942 – January 18, 2013) was an American computer scientist and ACM Fellow . Jim Horning received a PhD in computer science from Stanford University in 1969 for

162-459: A set of large data tables describing all legal combinations of the syntax rules and how to discern them. This table generation step is re-done only when the language is changed. When the compiler runs, those data tables are used by a small, language-independent parsing algorithm to parse and respond to the input language. This style of table-driven parser is generally easier to write than an entirely hand-written recursive descent parser. XCOM uses

189-412: A simple compiler. Compiler internals can be written easily in XPL, and the code is easy to read. The PL/I language was designed by an IBM committee in 1964 as a comprehensive language replacing Fortran , COBOL , and ALGOL , and meeting all customer and internal needs. These ambitious goals made PL/I complex, hard to implement efficiently, and sometimes surprising when used. XPL is a small dialect of

216-722: A thesis entitled A Study of Grammatical Inference . He was a founding member, and later chairman, of the Computer Systems Research Group at the University of Toronto , Canada, from 1969 until 1977. He collaborated in the design of the programming language Euclid there. He was then a research fellow at the Xerox Palo Alto Research Center (PARC) from 1977 until 1984 and a founding member and senior consultant at DEC Systems Research Center (DEC/SRC) from 1984 until 1996. He

243-584: A very simple strategy for disk direct access. NOTE provided the address of a disk track. POINT set the location of the next disk track to be the address previously returned by NOTE. This strategy was adopted to allow easy porting of XMON to other OSes, and to avoid the much more complicated disk direct access options available at that time. Converting XMON from its primitive use of NOTE, POINT and READ/WRITE disk operations—with precisely 1 block per track—to EXCP (i.e., write/create new records) and XDAP (i.e., read/update old records)—with n blocks per track, where n

270-412: Is a one-pass compiler using a table-driven parser and simple code generation techniques. Versions of XCOM exist for different machine architectures , using different hand-written code generation modules for those targets. The original target was IBM System/360 , which is a proper subset of IBM System/370 , IBM System/390 and IBM System z . XCOM compiles from XPL source code, but since XCOM itself

297-614: Is a similar exercise, except only the code generation modules need to be changed. XCOM is a one-pass compiler (but with an emitted code fix-up process for forward branches, loops and other defined situations). It emits machine code for each statement as each grammar rule within a statement is recognized, rather than waiting until it has parsed the entire procedure or entire program. There are no parse trees or other required intermediate program forms, and no loop-wide or procedure-wide optimizations. XCOM does, however, perform peephole optimization . The code generation response to each grammar rule

SECTION 10

#1732791041606

324-524: Is also not powerful enough to handle all likely grammars. It is applicable only when the language designer can tweak the language definition to fit MSP's restrictions, before the language is widely used. The University of Toronto subsequently changed XCOM and XA to instead use a variant of Donald Knuth 's LR parser bottom-up method. XCOM's variant is called Simple LR or SLR. It handles more grammars than MSP but not quite as many grammars as LALR or full LR(1) . The differences from LR(1) are mostly in

351-413: Is attached to that rule. This immediate approach can result in inefficient code and inefficient use of machine registers. Such are offset by the efficiency of implementation, namely, the use of dynamic strings mentioned earlier: in processing text during compilation, substring operations are frequently performed. These are as fast as an assignment to an integer; the actual substring is not moved. In short, it

378-425: Is itself a generalization of the trivially simple operator precedence methods that work nicely for expressions like A+B*(C+D)-E. MSP tables include a list of expected triplets of language symbols. This list grows larger as the cube of the grammar size, and becomes quite large for typical full programming languages. XPL-derived compilers were difficult to fit onto minicomputers of the 1970s with limited memories. MSP

405-418: Is quick, easy to teach in a short course, fits into modest-sized memories, and is easy to change for different languages or different target machines. The XCOM compiler has a hand-written lexical scanner and a mechanically-generated parser. The syntax of the compiler's input language (in this case, XPL) is described by a simplified BNF grammar . XPL's grammar analyzer tool ANALYZER or XA turns this into

432-443: Is required to build a compiler for a new language or new target. A better label for XPL is a translator writing system. It helps to write a compiler with less new or changed programming code. The XPL language is a simple, small, efficient dialect of PL/I intended mainly for the task of writing compilers. The XPL language was also used for other purposes once it was available. XPL can be compiled easily to most modern machines by

459-718: Is written in XPL it can compile itself – it is a self-compiling compiler , not reliant on other compilers. Several famous languages have self-compiling compilers, including Burroughs B5000 Algol, PL/I, C , LISP , and Java . Creating such compilers is a chicken-and-egg conundrum. The language is first implemented by a temporary compiler written in some other language, or even by an interpreter (often an interpreter for an intermediate code, as BCPL can do with intcode or O-code ). XCOM began as an Algol program running on Burroughs machines, translating XPL source code into System/360 machine code. The XPL team manually turned its Algol source code into XPL source code. That XPL version of XCOM

486-414: The XPL compiler writing system is an example compiler named SKELETON . This is just XCOM with parse tables for an example toy grammar instead of XPL's full grammar. It is a starting point for building a compiler for some new language, if that language differs much from XPL. XPL is run under the control of a monitor, XMON , which is the only operating system-specific part of this system, and which acts as

513-412: The compiler generates the following Z80 instructions for each procedure call: If there were two consecutive subroutine calls, they would look like this: The sequence POP regs followed by PUSH for the same registers is generally redundant. In cases where it is redundant, a peephole optimization would remove these instructions. In the example, this would cause another redundant POP/PUSH pair to appear in

540-450: The full language. XPL has one added feature not found in PL/I: a STRING datatype with dynamic lengths. String values live in a separate text-only heap memory space with automatic garbage collection of stale values. Much of what a simple compiler does is manipulating input text and output byte streams, so this feature helps simplify XPL-based compilers. The XPL compiler, called XCOM ,

567-563: The table generator's algorithms, not in the compile-time parser method. XCOM and XA predate the widespread availability of Unix and its yacc parser generator tool. XA and yacc have similar purposes. XPL is open source. The System/360 version of XPL was distributed through the IBM SHARE users organization. Other groups ported XPL onto many of the larger machines of the 1970s. Various groups extended XPL, or used XPL to implement other moderate-sized languages. XPL has been used to develop

SECTION 20

#1732791041606

594-424: The top of the stack ) is known/assumed to be more efficient than aload (which loads a local variable and pushes it onto the stack). The following source code : is straightforwardly compiled to: but can be optimized to: If the compiler saves registers on the stack before calling a subroutine and restores them when returning, consecutive calls to subroutines may have redundant stack instructions. Suppose

621-554: Was computed at run-time from the target device's physical characteristics and could be significantly greater than 1—achieved significantly improved application performance and decreased operating system overhead. Although originally developed for OS/360 , XMON (either the original NOTE, POINT and READ/WRITE implementation; or the EXCP and XDAP enhancement) will run on subsequently released IBM OSes, including OS/370, XA, OS/390 and z/OS , generally without any changes. XCOM originally used

648-579: Was founder and director of STAR Lab from 1997 until 2001 at Intertrust Technologies Corporation . Peter G. Neumann reported on 22 January 2013 in the RISKS Digest , volume 27, issue 14, that Horning had died on 18 January 2013 in Palo Alto, California/ Horning's interests included programming languages , programming methodology , specification , formal methods , digital rights management and computer/network security . A major contribution

675-494: Was his involvement with the Larch approach to formal specification with John Guttag ( MIT ) et al. Peephole optimization Peephole optimization is an optimization technique performed on a small set of compiler -generated instructions, known as a peephole or window, that involves replacing the instructions with a logically equivalent set that has better performance. For example: The term peephole optimization

702-471: Was introduced by William Marshall McKeeman in 1965. Peephole optimization replacements include but are not limited to: Modern compilers often implement peephole optimizations with a pattern matching algorithm . The following Java bytecode : can be replaced with the following which executes faster: As for most peephole optimizations, this is based on the relative efficiency of different instructions. In this case, dup (which duplicates and pushes

729-400: Was then compiled on Burroughs, creating a self-compiling XCOM for System/360 machines. The Algol version was then thrown away, and all further improvements happened in the XPL version only. This is called bootstrapping the compiler. The authors of XPL invented the tombstone diagram or T-diagram to document the bootstrapping process. Retargeting the compiler for a new machine architecture

#605394