{"entities":{"Q4040864":{"pageid":6070580,"ns":120,"title":"Item:Q4040864","lastrevid":108784976,"modified":"2026-11-10T06:52:05Z","type":"item","id":"Q4040864","labels":{"en":{"language":"en","value":"Parsing theory. Volume II: LR (k) and LL (k) parsing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 194074"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040864$8289810F-FFC6-413F-9A68-E797B656B0F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9bc9484eefe74c42a6911ac5dd6e79752529562","datavalue":{"value":"0703.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040864$2DA104A4-D15B-4A42-A926-C007BD9F0E29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba9f8735bf2fcb4687003c328c926a88d6607376","datavalue":{"value":{"entity-type":"item","numeric-id":794444,"id":"Q794444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040864$9B3F6761-8F85-4BCB-858C-8A9C177DCD05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f5ae3c40a239b0d91d4aa09f8b879d76f3f35d9","datavalue":{"value":{"entity-type":"item","numeric-id":199234,"id":"Q199234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040864$BB43541D-9041-4714-AE48-C04CFFFC9476","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28319e3934f5b194abbcd5639e9eae3758e9e43c","datavalue":{"value":{"time":"+1993-06-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4040864$B3A435A5-36F8-477C-B292-B6CC8CBC0122","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040864$6F17E5E3-02A3-43F0-8217-30ABE1C0E4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040864$4180363C-2E49-4646-885A-0EE4F00380E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ca521e96f5dcfa9f0240b659cb77d27128546c3","datavalue":{"value":"194074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4040864$0F6F1EA1-F345-491D-84BC-934CCA0EBDDA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0be4b75e65571e4b373b4c198a8f27230f760447","datavalue":{"value":"LR(k) and LL(k) parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040864$C281EFA4-8D97-42D3-BD26-317F67B1D2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e0b54e0920d7c687a79ce5dece47d40ea921492","datavalue":{"value":"parsing theory of context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040864$0DFAB624-9143-4E53-941F-3DA030BBE4ED","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4040864$884DB7DA-539E-46D7-8F68-BA198CC3F4FD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eacbb4852996443de36b05bd27d07aec454906f3","datavalue":{"value":{"entity-type":"item","numeric-id":3325071,"id":"Q3325071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ef0121a25080b7886a89691eb079f4033129a85","datavalue":{"value":{"amount":"+0.8841262459754944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040864$F3687743-81BE-40D0-B2FF-B4CA99C69C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cfeddef1c458f95893ff9951f1557551f45b8b7","datavalue":{"value":{"entity-type":"item","numeric-id":3826121,"id":"Q3826121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5718b5f643ca272864045bb9f88d91e58fd0b484","datavalue":{"value":{"amount":"+0.8835362792015076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040864$52FE6509-147B-4398-8FDB-3BB8E61DFB4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dfbe29330c01f53f050ae9e59395fb691f634a0","datavalue":{"value":{"entity-type":"item","numeric-id":4040284,"id":"Q4040284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d750d94945f9aed0e4f949a8b4e44f99cd1b6905","datavalue":{"value":{"amount":"+0.8445201516151428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040864$D6FDD507-A198-4BFA-9D72-1CD0AA979B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3da4e975414f02e1bd55b92d7fa694cdedd79ac3","datavalue":{"value":{"entity-type":"item","numeric-id":5402518,"id":"Q5402518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2da3e05f29a70f063a4f8cc10f57950e7b8c6a5","datavalue":{"value":{"amount":"+0.8411324620246887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040864$0039ABFE-4687-4514-A10F-A92B9FFDADFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ffbfe107322a1164d3c7776462a92c91f78fb15","datavalue":{"value":{"entity-type":"item","numeric-id":3587436,"id":"Q3587436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"374b548f23a05dda22e666757c7d4a747435b10a","datavalue":{"value":{"amount":"+0.8345116376876831","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4040864$47B705BD-7D94-4FE0-9C74-192C8964D836","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cdd20bd83aad8d6ce9491d01d7f8157f0f9638c5","datavalue":{"value":{"text":"Parsing theory. Volume II: LR (k) and LL (k) parsing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4040864$6ACD363E-4949-418E-87A5-1760ECD2908D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"89b06411aaedb024c1daac84ff6e371045f3dc4a","datavalue":{"value":"The authors' preface to this second volume of the monograph represents a very good pattern for a concentrated but comprehensive review to the book. We shall follow it in certain respects. Chapter 6 (Chapters 1-5 belong to Vol. I) presents the classical constructions of LR(k) parsing. These constructions include the canonical LR(k) parser (a right parser which uses \u1e35-length lookahead strings and whose stack strings consist of equivalent classes of viable prefixes), and its reduced variants such as the LALR(k) and SLR(k) parsers. Formal properties of the corresponding LR(k), LALR(k), and SLR(k) grammars are investigated. All the results are provided with detailed mathematical proofs. Chapter 7 is devoted to practical issues involved in the construction and use of deterministic LR(1) parsers. Constructions of the LR(0), SLR(1), canonical LR(1), and LALR(1) parsers are given. An efficient algorithm for determining the lookahead symbols for the ``reduce'' actions of an LALR(1) parser is considered. There are developed methods for optimizing LR(0)-based LR(1) parsers on the basis of inessential error entries. Detailed algorithms are given, and used to merge compatible states of the parser and to eliminate reductions by unit rules from the parser. Finally for this section, LR(1) parsers for ambiguous grammars are considered. In Chapter 8 there is generalized the strong LL(k) to canonical LL(k) (and LALL(k)) parsers, defined as counterparts of the canonical LR(k) (and LALR(k)) parsers. The (duality) relationship between the LL(k) and LR(k) grammars is studied, and methods for transforming LR(k) into LL(k) grammars are provided. Chapter 9 analyses algorithms for (syntax) error recovery in LL(1) and LR(1) parsing, as well as syntax error reporting. Chapter 10 is studying the computational complexity of testing grammars for (LR(k), LL(k), LALR(k) etc.) parsability. Efficient polynomial-time algorithms are developed for LR(k), SLR(k), LL(k), and SLL(k), with \u1e35 fixed, upper and lower bounds for LALR(k) and LALL(k) are established. Complexity results are given in case \u1e35 is a parameter of the testing problems. A final remark: each chapter ends with substantial and very useful sets of exercises, and conversant bibliographic notes. As in every monograph, it can not cover everything in the field, but essentially is that the book thoroughly cover the classical topics with complete mathematical accuracy. The present monograph can be labeled as a serious and useful construction, instrument, and guide for all that study or apply parsing, from compiler construction to natural language processing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4040864$2537CD1B-0F8D-44A7-8152-00C3CAAB550F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parsing theory. Volume II: LR (k) and LL (k) parsing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parsing_theory._Volume_II:_LR_(k)_and_LL_(k)_parsing"}}}}}