Editing XPL (section)

==Parsing==
XCOM originally used a now-obsolete bottom-up parse table method called ''[[Shift-reduce parser#MSP|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 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.<ref group="nb">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 [[Z80]] microcomputer which had only 48 kilobytes of internal memory ([[DRAM]]) and only 100 kilobytes of external memory ([[floppy disk]]) running under [[CP/M]]. This version was completed in 1980. Porting to MacOS (9, later X) was subsequently completed.</ref>  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.

The [[University of Toronto]] subsequently changed XCOM and XA to instead use a variant of [[Donald Knuth]]'s [[LR parser]] bottom-up method.<ref group="nb">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 authors.</ref>  XCOM's variant is called [[SLR parser|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 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 (computing)|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.