{"entities":{"Q805244":{"pageid":807092,"ns":120,"title":"Item:Q805244","lastrevid":42705465,"modified":"2025-07-08T16:40:09Z","type":"item","id":"Q805244","labels":{"en":{"language":"en","value":"A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4203732"}},"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":"Q805244$82FC9F12-3BDB-47B8-8494-70D25C0A2A00","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"464cf748e7aaaa39833e09d1160798d7f430abb1","datavalue":{"value":{"text":"A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805244$17B0518B-86B7-4CAF-A7C8-574FE66D1FB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aec92129c7716ebb56cfbc44717ffeebc28fcbd0","datavalue":{"value":"0728.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$DE999A6E-06B6-4085-8928-87C341B62306","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41debdd550b2e942c372c653a4e78b3f2e7dfc75","datavalue":{"value":"10.1016/0304-3975(91)90180-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$C7C7BD74-E133-42E7-9580-F03CBDBB62C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"131029ce53ddb08bb6d9bd0beb1bf65ac7a8e6de","datavalue":{"value":{"entity-type":"item","numeric-id":805243,"id":"Q805243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$92C43748-D36B-4027-A1B0-DF914B658063","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$26C5D4C5-C94B-4A0D-9456-D67CD35E838D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q805244$7E051465-DF0C-40FA-94E9-061B8081CA11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fb9f87b9d496307ead5706eef1d198fc139b3e1d","datavalue":{"value":"The paper demonstrates that by a slight change in the Early's algorithm a O(n) time performance for every LR(k) grammar can be obtained without use of lookahead. This was conjectured by Early in his PhD Thesis [Commun. ACM 13, No.2, 94-102 (1970; Zbl 0185.434 (01))].    A new algorithm for recognition of general context-free languages is proposed. Like Early's algorithm it takes \\(O(n^ 3)\\) time when it runs on general context-free grammars. But it runs in O(n) time and space for the large class of LR regular grammars, (an extension of LR(k) grammars). This is the main theoretical result of the paper and a sketch of its proof is presented.    The paper contains also an informal description of the algorithm as well as a comparative example on a simple grammar with this algorithm and Early's algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q805244$C90F55E9-02AD-46C7-8E45-C2766AA49F27","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$E13D5429-3024-4645-AEA2-415D9C9F5FE7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15b6bd12b4f4eb25a9899e1c8fe99cd748e5a47b","datavalue":{"value":"4203732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$B1899D1D-5193-4312-85CA-447DB668720D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd16814091e55538d925abdd9e69d89accc54a27","datavalue":{"value":"parsing algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q805244$58760824-ABBE-4FFE-BD15-E8D0FD56C56D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a55fb7e70a0a30faba9d447ff633fcbf884168f","datavalue":{"value":"linear complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q805244$5084BC86-4EF5-4A38-950D-F459A46BE05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e00a87a4852ff4ffa94e5664a9345e455b8985a9","datavalue":{"value":"LR regular grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q805244$D8916157-41B7-4323-A44D-F27CE7654982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09a68137d8e680a434ada0e25d31c16d68b045fc","datavalue":{"value":"LR(k) grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q805244$861A5DCA-8E64-4FCA-9B0E-BD484748CD1F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e04307a3acdc46952a7e6b9a2dcbe9eee68661a3","datavalue":{"value":"Q56047567","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$148B169E-D9CA-4E4B-9F82-A8EA0D245606","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":"Q805244$0B0D5EF6-76BE-42B5-9439-576A34BD726C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e37d3cd89bf56058a2b19db5dd9a0a78bfe825f","datavalue":{"value":{"entity-type":"item","numeric-id":2561843,"id":"Q2561843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$0ECC3609-D97D-43CB-8E46-4516832421B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff20cbe58cba04c9bd812baaf2c28b648c83661","datavalue":{"value":{"entity-type":"item","numeric-id":2558004,"id":"Q2558004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$FDD6594C-F7D8-46B6-9017-C7BB5BD496C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b216d2441e615eeb3b52d37ecd97ca01e34429","datavalue":{"value":{"entity-type":"item","numeric-id":4062666,"id":"Q4062666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$17BE3AA9-4F10-4BB7-85BB-C05A7AD5C8B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b78adcee74e0f5ade00e0948eea875c91d9521e5","datavalue":{"value":{"entity-type":"item","numeric-id":5578055,"id":"Q5578055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$B13AF95C-95B6-450A-9B63-C3D44108ACEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eee975ef5deaf81238105e966c5726499b315f80","datavalue":{"value":{"entity-type":"item","numeric-id":3911426,"id":"Q3911426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$76478B69-59B0-41BC-8819-D2D38A4FCEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$DD1439F9-EBE7-414D-9A94-01A3DBEC1279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79e03cd8581db3f1a993a90df4b9b3924df0ec8d","datavalue":{"value":{"entity-type":"item","numeric-id":5528645,"id":"Q5528645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805244$7E90A41F-4217-470B-BC6E-6541A448C840","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dc1fba0f75e066f817be06bf7595b0c8320d82c","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90180-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q805244$725EB8FB-BA90-49F5-955A-C9C7DEB54162","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"27e204b8fb8fc60e22cb0d6b8607a410963136ea","datavalue":{"value":"W2058476719","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$6BF973C8-0D9D-46D6-8DFF-BC07AFAB9DCA","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"2656799ec802b861540c0996d131d49c1e36b84f","datavalue":{"value":"journals/tcs/Leo91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805244$3076BBB7-0C39-4D4D-9EC9-9268154D4719","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88239949e80135b364d6c3666a295039e005ac9b","datavalue":{"value":{"entity-type":"item","numeric-id":5203697,"id":"Q5203697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75f214cdb7f5b53a91dbf1d52780dd2214c494c3","datavalue":{"value":{"amount":"+0.89256644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$F483D2DC-4814-45D2-8F63-566866BBF6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"887209d1356cef8f7c789512c8d210df877807e3","datavalue":{"value":{"entity-type":"item","numeric-id":671525,"id":"Q671525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23d49673ed97fccdd48b964e14b406db5e2f95f2","datavalue":{"value":{"amount":"+0.87212545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$9D52D2F7-3A87-4B08-A199-4BD3033EB9ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0af085b121af1124c5dfefa809106f5aad9b8b2","datavalue":{"value":{"entity-type":"item","numeric-id":757072,"id":"Q757072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b139a0a50cd2fb561ca48dcfe15a85637c90915","datavalue":{"value":{"amount":"+0.86408174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$9E71061A-35BC-4FC7-A7E0-6A5B1D11B7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0d450eed341dea66eded4983d2906cac8a4f0f5","datavalue":{"value":{"entity-type":"item","numeric-id":4028904,"id":"Q4028904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e97df40ecfdf6864047b3705a35d6920fb48306c","datavalue":{"value":{"amount":"+0.8640816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$ADB5D449-142D-4A25-9FF3-9CA5CCF450FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"369065c4935c7cc6ddaf29f808c7403a842e71f7","datavalue":{"value":{"entity-type":"item","numeric-id":1350210,"id":"Q1350210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d70874a312ae710faf2bafacd7943da39f07e77","datavalue":{"value":{"amount":"+0.86377597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$77FF0DFB-DE6B-45B6-8A06-403B310582BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62a08afbf6b9420e0a3c4ec7f9240b3fc7fe0c6a","datavalue":{"value":{"entity-type":"item","numeric-id":5285112,"id":"Q5285112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3757046ad1524e7b84a8fb6a93a1f8d6b1e0c504","datavalue":{"value":{"amount":"+0.85836077","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$11E734C4-AF08-4F76-A960-40EFFF4D2396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e640e378f87294ba0762d440023f2598be13a30","datavalue":{"value":{"entity-type":"item","numeric-id":4062666,"id":"Q4062666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21e9aa1abcfbf1140eb9597cc6d0b37fcbfa1435","datavalue":{"value":{"amount":"+0.855919","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$2634404A-640F-40E6-9B19-95778E325CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cbb71a44d9aaa6c78acb8fdd7bae0d4b3a9d32c","datavalue":{"value":{"entity-type":"item","numeric-id":2411044,"id":"Q2411044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"617180bc5490a35a1f7986d001a16d31b31a48bb","datavalue":{"value":{"amount":"+0.8528497","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$55C2650C-A8B9-4606-A787-19FADCE09678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31c26e421a047313567a407e4d424e7bf52ff641","datavalue":{"value":{"entity-type":"item","numeric-id":848238,"id":"Q848238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12db619a6e506c29564c822c1d58320ab756151a","datavalue":{"value":{"amount":"+0.8510939","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$0B220173-3DD0-4800-8BAD-51495B608B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69f0906d03c6a21942828827a3766718928c204e","datavalue":{"value":{"entity-type":"item","numeric-id":5958725,"id":"Q5958725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edda4da43d9f93b3d26bf0e966ad008071bc90c3","datavalue":{"value":{"amount":"+0.8500763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805244$D27DE732-D284-43FA-9192-2239DC1326D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:805244","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:805244"}}}}}