236:. The code generation response to each grammar rule 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 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.
310:, which is the only operating system-specific part of this system, and which acts as 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
260:
turns this into 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
97:
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 a simple compiler. Compiler internals can be written easily in XPL, and the code is easy to read. The PL/I language was
386:
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
209:
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 was then compiled on Burroughs, creating a self-compiling XCOM for System/360
231:
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,
317:
XMON used 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
329:(i.e., read/update old records)—with n blocks per track, where n 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.
387:
minicomputers of the 1970s with limited memories. MSP 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.
114:, 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 the full language. XPL has one added feature not found in PL/I: a
194:. 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
493:
Ancona, Massimo, Dodero, Gabriella, and
Durante, Ercole Luigi "Cross software development for microprocessors using a translator writing system" Proceedings of the 4th International Conference on Software Engineering 1979:
512:
McKeeman, W. M., Horning, James J., Nelson, E. C., and
Wortman, D. B. "The XPL compiler generator system." AFIPS Conference Proceedings: 1968 Fall Joint Computer Conference. Washington DC: The Thompson Book Company. 1968:
80:
They called the combined work a 'compiler generator'. But that implies little or no language- or target-specific programming is required to build a compiler for a new language or new target. A better label for XPL is a
584:
This version was NOT released to the general community, hence it remains proprietary to its authors, or to their institutions. Repeated requests for an SLR(1) or an LALR(1) distribution of XPL have been ignored by its
49:
tool for easily implementing similar compilers for other languages. XPL was designed in 1967 as a way to teach compiler design principles and as starting point for students to build compilers for their own languages.
873:
558:
Indeed, using a hand-written LALR-like analyzer and a particularly efficient "decomposition" procedure for the produced parsing tables, it was possible to generate a parser for the entire XPL language on a 2 MHz
516:
Sitton, Gary A., Kendrick, Thomas A., and
Carrick, Jr., A. Gil. "The PL/EXUS Language and Virtual Machine" Proceedings of the ACM-IEEE Symposium on High-level-language Computer Architecture Nov, 1973: 124-130.
298:. 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.
269:
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
464:
used a variant of XPL, called "Scientific XPL" for their ABLE series computers, used for laboratory automation, computer networking, and control of music synthesis hardware, starting in the mid-1970s
414:. The differences from LR(1) are mostly in the table generator's algorithms, not in the compile-time parser method. XCOM and XA predate the widespread availability of Unix and its
425:
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.
314:. 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.
336:, 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,
519:
Slimick, John "Current
Systems Implementation Languages: One User's View" Proceedings of the SIGPLAN symposium on Languages for system implementation Oct, 1971: 20-28.
522:
Storm, Mark W., and Polk, Jim A. "Usage of an XPL Based
Compiler Generator System" Proceedings of the 14th annual ACM Southeast Regional Conference April 1976: 19-26.
126:
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.
54:
437:
678:
286:
for allocating and garbage-collecting XPL string values. The source code for this library must be included into most every program written in XPL.
58:
916:
227:
XCOM is a one-pass compiler (but with an emitted code fix-up process for forward branches, loops and other defined situations). It emits
506:
Leach, Geoffrey and Golde, Helmut. "Bootstrapping XPL to an XDS Sigma 5 Computer." Software: Practice and
Experience 3 (1973): 235-244.
261:
parse and respond to the input language. This style of table-driven parser is generally easier to write than an entirely hand-written
911:
906:
896:
274:
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.
199:
248:
and a mechanically-generated parser. The syntax of the compiler's input language (in this case, XPL) is described by a simplified
311:
448:
526:
210:
machines. The Algol version was then thrown away, and all further improvements happened in the XPL version only. This is called
901:
224:
the compiler for a new machine architecture is a similar exercise, except only the code generation modules need to be changed.
509:
McKeeman, William M., Horning, James J. and
Wortman, David B. A Compiler Generator. Englewood Cliffs, NJ: Prentice-Hall, 1970.
490:
Alexander, W. G. and
Wortman, D. B. "Static and Dynamic Charactersistics of XPL Programs." IEEE Computer November 1975; 41-46.
850:
123:
456:
321:
Converting XMON from its primitive use of NOTE, POINT and READ/WRITE disk operations—with precisely 1 block per track—to
19:
This article is about a dialect of the PL/I programming language. For the meaning of the term and other uses, see
921:
500:
Karger, Paul A. "An
Implementation of XPL for Multics." SB thesis. Massachusetts Institute of Technology, 1972.
70:
671:
366:
include later-released "peephole optimizations" and additional data types which were developed outside of the
326:
174:
XCOM compiles from XPL source code, but since XCOM itself is written in XPL it can compile itself – it is a
607:
452:
191:
748:
148:
641:
497:
Kamnitzer, S. H. "Bootstrapping XPL from IBM/360 to UNIVAC 1100." ACM SIGPLAN Notices May 1975: 14-20.
672:"Computer Connections: People, Places, and Events in the Evolution of the Personal Computer Industry"
211:
115:
178:, not reliant on other compilers. Several famous languages have self-compiling compilers, including
371:
183:
155:, using different hand-written code generation modules for those targets. The original target was
649:
575:. This version was completed in 1980. Porting to MacOS (9, later X) was subsequently completed.
82:
391:
354:
233:
119:
503:
Klumpp, Allan R. "Space Station Flight Software: Hal/S or Ada?" Computer March 1985: 20-28.
34:
20:
8:
819:
461:
383:
85:
writing system. It helps to write a compiler with less new or changed programming code.
66:
807:
663:
853:. The definitive reference, including source code of all components of the XPL system.
823:
433:
XPL has been used to develop a number of compilers for various languages and systems.
846:
422:
266:
262:
215:
42:
811:
622:
421:
XPL is open source. The System/360 version of XPL was distributed through the IBM
271:
245:
46:
881:
770:
179:
152:
294:
The last piece of the XPL compiler writing system is an example compiler named
164:
160:
156:
890:
667:
406:
or SLR. It handles more grammars than MSP but not quite as many grammars as
375:
815:
395:
228:
168:
118:
datatype with dynamic lengths. String values live in a separate text-only
882:
Scientific XPL for New England Digital Corporation's ABLE Series Computers
729:
626:
775:
568:
249:
221:
73:. The methods and compiler are described in detail in the 1971 textbook
62:
382:. Simple precedence is itself a generalization of the trivially simple
352:
XCOM originally used a now-obsolete bottom-up parse table method called
403:
841:
McKeeman, William Marshall; Horning, James J.; and Wortman, David B.,
399:
784:
780:
863:
474:
103:
337:
333:
318:
complicated disk direct access options available at that time.
203:
144:
563:
microcomputer which had only 48 kilobytes of internal memory (
478:
442:
411:
394:
subsequently changed XCOM and XA to instead use a variant of
379:
111:
107:
805:
608:"Current Systems Implementation Languages: One User's View"
572:
564:
539:
418:
parser generator tool. XA and yacc have similar purposes.
415:
407:
341:
322:
195:
187:
94:
38:
868:
93:
The XPL language is a simple, small, efficient dialect of
560:
473:
XPL continues to be ported to current computers. An x86/
99:
102:
committee in 1964 as a comprehensive language replacing
370:
implementation team.) MSP is a generalization of the
734:
Department of Computer Science, University of Toronto
218:
or T-diagram to document the bootstrapping process.
808:"Announcing the initial release of an XPL Compiler"
481:port in 2015, and an XPL to C translator in 2017.
806:shoefoot (Daniel E. Weaver) (November 21, 2017).
445:, the language used for the Space Shuttle program
151:techniques. Versions of XCOM exist for different
888:
214:the compiler. The authors of XPL invented the
143:, is a one-pass compiler using a table-driven
567:) and only 100 kilobytes of external memory (
402:bottom-up method. XCOM's variant is called
362:released version retains the MSP parser and
656:
633:
306:XPL is run under the control of a monitor,
358:, invented by the XPL team (although the
529:ACM SIGPLAN Notices January 1978: 70-74.
455:used by General Motors to develop their
16:Dialect of the PL/I programming language
769:Weaver, Daniel E. (November 21, 2017).
749:"Dave Bodenstab's Home Page (archived)"
662:
639:
605:
889:
768:
677:(Manuscript, part 1). Kildall Family.
69:. XPL was first announced at the 1968
917:Programming languages created in 1967
746:
325:(i.e., write/create new records) and
244:The XCOM compiler has a hand-written
457:Multiple Console Time Sharing System
53:XPL was designed and implemented by
864:University of Toronto XPL Home Page
771:"XPL compiler: XPL to C translator"
45:written in its own language, and a
13:
719:A Compiler Generator Appendix A1,7
527:"A roster of XPL implementations."
332:Although originally developed for
14:
933:
857:
468:
344:, generally without any changes.
912:Structured programming languages
907:Procedural programming languages
897:PL/I programming language family
642:"In His Own Words: Gary Kildall"
799:
762:
740:
684:from the original on 2020-06-24
484:
428:
252:. XPL's grammar analyzer tool
722:
713:
710:A Compiler Generator, page 372
704:
695:
606:Slimick, John (October 1971).
599:
578:
552:
477:port was done in 2000, an x86/
159:, which is a proper subset of
71:Fall Joint Computer Conference
1:
902:Systems programming languages
701:A Compiler Generator page 251
592:
129:
31:expert's programming language
869:The XPL Programming Language
122:memory space with automatic
7:
670:; Kildall, Kristin (eds.).
640:Shustek, Len (2016-08-02).
533:
453:system programming language
289:
239:
88:
10:
938:
730:"The Development of Hal/S"
347:
277:
18:
355:Mixed Strategy Precedence
139:The XPL compiler, called
545:
372:simple precedence parser
650:Computer History Museum
301:
284:runtime support library
282:XPL includes a minimal
176:self-compiling compiler
134:
922:Programming languages
627:10.1145/942596.807056
392:University of Toronto
265:parser. XCOM uses a
234:peephole optimization
153:machine architectures
875:A Compiler Generator
843:A Compiler Generator
75:A Compiler Generator
35:programming language
21:XPL (disambiguation)
664:Kildall, Gary Arlen
615:ACM SIGPLAN Notices
462:New England Digital
384:operator precedence
374:method invented by
67:Stanford University
55:William M. McKeeman
877:page at Amazon.com
438:Stony Brook Pascal
124:garbage collection
851:978-0-13-155077-3
747:Bodenstab, Dave.
646:Remarkable People
267:bottom-up parsing
263:recursive descent
216:tombstone diagram
43:one-pass compiler
929:
834:
833:
831:
829:
803:
797:
796:
794:
792:
766:
760:
759:
757:
755:
744:
738:
737:
726:
720:
717:
711:
708:
702:
699:
693:
692:
690:
689:
683:
676:
660:
654:
653:
637:
631:
630:
612:
603:
586:
582:
576:
571:) running under
556:
63:James J. Horning
59:David B. Wortman
47:parser generator
937:
936:
932:
931:
930:
928:
927:
926:
887:
886:
860:
838:
837:
827:
825:
804:
800:
790:
788:
767:
763:
753:
751:
745:
741:
728:
727:
723:
718:
714:
709:
705:
700:
696:
687:
685:
681:
674:
666:(2016-08-02) .
661:
657:
638:
634:
610:
604:
600:
595:
590:
589:
583:
579:
557:
553:
548:
536:
525:Wortman, D. B.
487:
471:
431:
350:
304:
292:
280:
246:lexical scanner
242:
180:Burroughs B5000
149:code generation
137:
132:
98:designed by an
91:
24:
17:
12:
11:
5:
935:
925:
924:
919:
914:
909:
904:
899:
885:
884:
879:
871:
866:
859:
858:External links
856:
855:
854:
836:
835:
816:comp.compilers
798:
761:
739:
721:
712:
703:
694:
668:Kildall, Scott
655:
632:
597:
596:
594:
591:
588:
587:
577:
550:
549:
547:
544:
543:
542:
535:
532:
531:
530:
523:
520:
517:
514:
510:
507:
504:
501:
498:
495:
491:
486:
483:
470:
469:Current status
467:
466:
465:
459:
446:
440:
430:
427:
349:
346:
303:
300:
291:
288:
279:
276:
241:
238:
165:IBM System/390
161:IBM System/370
157:IBM System/360
136:
133:
131:
128:
90:
87:
65:and others at
15:
9:
6:
4:
3:
2:
934:
923:
920:
918:
915:
913:
910:
908:
905:
903:
900:
898:
895:
894:
892:
883:
880:
878:
876:
872:
870:
867:
865:
862:
861:
852:
848:
844:
840:
839:
824:
821:
817:
813:
809:
802:
786:
782:
778:
777:
772:
765:
750:
743:
735:
731:
725:
716:
707:
698:
680:
673:
669:
665:
659:
651:
647:
643:
636:
628:
624:
620:
616:
609:
602:
598:
581:
574:
570:
566:
562:
555:
551:
541:
538:
537:
528:
524:
521:
518:
515:
511:
508:
505:
502:
499:
496:
492:
489:
488:
482:
480:
476:
463:
460:
458:
454:
450:
447:
444:
441:
439:
436:
435:
434:
426:
424:
419:
417:
413:
409:
405:
401:
397:
393:
388:
385:
381:
377:
376:Niklaus Wirth
373:
369:
365:
361:
357:
356:
345:
343:
339:
335:
330:
328:
324:
319:
315:
313:
309:
299:
297:
287:
285:
275:
273:
268:
264:
259:
255:
251:
247:
237:
235:
230:
225:
223:
219:
217:
213:
212:bootstrapping
207:
205:
201:
197:
193:
189:
185:
182:Algol, PL/I,
181:
177:
172:
170:
166:
162:
158:
154:
150:
146:
142:
127:
125:
121:
117:
113:
109:
105:
101:
96:
86:
84:
78:
76:
72:
68:
64:
60:
56:
51:
48:
44:
41:, a portable
40:
36:
32:
28:
22:
874:
842:
826:. Retrieved
801:
789:. Retrieved
774:
764:
752:. Retrieved
742:
733:
724:
715:
706:
697:
686:. Retrieved
658:
645:
635:
621:(9): 20–28.
618:
614:
601:
580:
554:
485:Bibliography
472:
432:
429:Applications
420:
396:Donald Knuth
389:
367:
363:
359:
353:
351:
331:
320:
316:
307:
305:
295:
293:
283:
281:
257:
253:
243:
229:machine code
226:
220:
208:
198:can do with
175:
173:
169:IBM System z
140:
138:
92:
79:
74:
52:
30:
26:
25:
828:December 6,
791:December 6,
776:SourceForge
569:floppy disk
250:BNF grammar
222:Retargeting
147:and simple
891:Categories
688:2016-11-17
593:References
360:officially
130:Components
83:translator
812:Newsgroup
404:Simple LR
400:LR parser
312:IBM 2311s
37:based on
845:(1971),
785:Slashdot
781:La Jolla
679:Archived
585:authors.
534:See also
513:617-635.
494:399-402.
410:or full
368:original
364:does not
296:SKELETON
290:SKELETON
272:top-down
254:ANALYZER
240:ANALYZER
232:perform
89:Language
820:Usenet:
814::
754:Sep 13,
475:FreeBSD
348:Parsing
278:Runtime
200:intcode
104:Fortran
849:
822:
783:, CA:
338:OS/390
334:OS/360
204:O-code
190:, and
145:parser
116:STRING
110:, and
29:, for
787:Media
682:(PDF)
675:(PDF)
611:(PDF)
546:Notes
479:Linux
449:MALUS
443:HAL/S
423:SHARE
412:LR(1)
380:PL360
112:ALGOL
108:COBOL
33:is a
847:ISBN
830:2017
793:2017
756:2024
573:CP/M
565:DRAM
540:PL/M
451:, a
416:yacc
408:LALR
390:The
378:for
342:z/OS
340:and
327:XDAP
323:EXCP
308:XMON
302:XMON
196:BCPL
192:Java
188:LISP
167:and
141:XCOM
135:XCOM
120:heap
95:PL/I
39:PL/I
623:doi
561:Z80
398:'s
256:or
206:).
202:or
100:IBM
27:XPL
893::
818:.
810:.
779:.
773:.
732:.
648:.
644:.
617:.
613:.
258:XA
186:,
171:.
163:,
106:,
77:.
61:,
57:,
832:.
795:.
758:.
736:.
691:.
652:.
629:.
625::
619:6
184:C
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.