459:(which was short). But my email at home is busted so I can't put it here yet. *sigh*. LALR stands for Lookahead LR and is a method for producing LR parsers. LR stands for Left-to-right scan, Rightmost derivation. 2nd ed Dragon does not use the term LALR parser, and neither do I so I'm not sure what one is; I assume it is an LR parser produced by the LALR method? Sorry I used the term "rubbish" because the original entry certainly is not. --
151:
74:
53:
22:
487:, p. 24) that the "LL" and "LR" naming convention was introduced by Knuth. Might also mention that the "LR" in stands for "L" = "Left-to-Right" and "R" = "Rightmost production", and explain what that means. BTW, the "Gold", "Anagram", etc., software packages are LALR. You might want to add some references:
882:
The confusion about XPL's date is because the initial implementation of XPL used a different parser generator based on "extended mixed strategy precedence", a type of precedence parser. XPL switched over to the more powerful LALR methods a few years later. That happened at UC Santa Cruz, so DeRemer
516:
About LR parser versus LALR parser ... The parsing algorithm for an LALR parser is actually different than the parsing algorithm for an LR parser. An LALR parser has to save the reductions it makes in case of error recovery, whereas an LR parser does not have to save the reductions (it does not make
773:
for merging. The resultant article would have to have two enormous sections within it that are quite separate. You might argue (with some justification) that this is the most readable article structure -- however these are still two different topics, on two different tools, and need to be treated as
760:
an alternative name. No question about it. The two concepts are quite different: one is a tool, the another is a different tool, used to make examples of the first (it's easier to do it this way). There is no justification to merge because they're "the same thing" or "alternate names". That's simply
465:
A parser constructed by the LALR technique has tables the size of an LR(0) parser, yet is far more powerful and useful, which I think makes it a legitimate parser classification. It is also common enough (being produced by YACC) that the classification is useful in practice. The term "LALR parser"
969:
I am making this request because
Knowledge is for public consumption, not just for us compugeeks. The terminology and the complexity of the sentences in the introduction that a normal person would probably go catatonic trying to figure out what it meant and, if that didn't happen, they'd spend the
520:
Finally ... LALR parsers can be used for context-sensitive languages, like C++, if the parser generator has advanced capability for integrating symbol-table lookups with dynamic grammar symbols. I'm pretty sure ANTLR has this capability. I know that my parser generator has this advanced feature.
799:
have distinct use cases because nobody writes LALR parsers by hand except when working out textbook examples: every LALR parser is produced by an LALR parser generator, and every LALR parser generator produces LALR parsers. Most importantly, an LALR parser, an SLR parser, and an NQLALR parser are
863:
The article used to read "The original and most widely known parser generator was yacc, developed on the UNIX operating system." The "LALR Parser
Generator" article (LALR_parser_generator) gave dates for XPL as 1970 and yacc as 1975. I changed the date for XPL there to 1968 to correspond to the
505:
I just rewrote most of the article, trying to keep the previous text in the article when appropriate. This is a confusing subject for many people and I would like to have an accurate and precise article in
Knowledge, so that people can use it to understand the subject. I have about 30 years of
620:
I think it's OK to have a separate page for LALR parser generator. A program that generates a parser is quite different from a parser. People have a lot of trouble figuring out this concept, computer generated software. If the two drastically different programs are combined into one page, the
878:
DeRemer implemented the first LALR parser generator as part of his thesis that invented LALR. He then turned that parser generator into the core component of a proprietary compiler writing system called
Metaware, sold and supported by his company of that name. Metaware was coded in their own
172:
429:
So there's some precedent for calling something an "LALR parser" since they did it throughout the book and there are five citations, some of them multi-page, in the index for that phrase. I didn't create the initial entry, but I was kinda irked at the tone of the comment
879:
dialect of Pascal. Yacc, written in C, was developed by
Stephen Johnson of AT&T Bell Labs, from published articles and maybe DeRemer's excellent thesis. I don't know if the early Metaware generator preceded or followed the initial implementation of yacc.
437:
Okay. I am intending to use my Dragon Book when I write the article so no doubt I would've found all this out anyway. "Recursing on the rightmost non-terminal in any grammar rule" is not really a good definition of producins a rightmost derivation BTW.
406:. Immediate issues: LALR is an algorithm for generating tables for a table driven LR shift reduce parser. It is not a parser (ooh except maybe the Natural Language community think it is). pretty sure the derivation of each of the letters is wrong.))
648:
parser generators are distinct from, have quite different use cases, and have a very different history. If we develop these articles to a size where they'll cover the same ground, they'll also have enough detail to be even more distinct.
804:
arise from the manner in which the parsers were generated, so there is nothing interesting to be said about LALR parsers besides how they are generated. I still think merging these articles makes more sense than keeping them separate.
864:
original FJCC paper, but in either case yacc is not the "original" unless an earlier date is established, so I deleted this sentence. I'd accept "most widely known," except that now there are lots, starting with Gnu Bison.
970:
next 6 years learning all the terminology necessary just to start to understand it. A bit of hyperbole, actually, but I think you get my point. PLEASE "dumb down" the explanation for the mere mortals. Thanks!!!!
741:. But after I checked "what links here" and found the merger discussion I thought that I'd instead let you know that your opportunity to shine, and to demonstrate what you envisaged last year, has come. ☺
764:
There is an argument (which I don't support, but I do recgonise it) that these are very closely related. One indeed cannot exist without the other. If we also recognise that the current article state (NB,
506:
experience implementing an LALR parser generator, so I have first hand knowledge of this subject. It was a long hard learning experience and I offer my explanations for the benefit of others.
196:
336:
827:
The article gives some idea of what an LALR parser is (well, this is obvious enough when the acronym is expanded). But LALR(1) and LALR(2) are then mentioned — what are these?
253:
191:
1161:
114:
480:
How about some information on DFA and state transition? Maybe a comparison to LL and LR parsing techniques? Niklaus Wirth states (in his book "Compiler
Construction",
124:
1166:
1075:
1071:
1057:
795:
have different history from LALR parser generators. They were both invented in theory in 1969 by Frank DeRemer, and in practice during the 1970s. They also do
448:
seemed to imply. I agree recursing isn't the best way to describe it. Hm.. maybe I should go look at the stuff I said was rubbish and make sure I wasn't wrong.
90:
1156:
298:
703:
698:
707:
272:
1033:
690:
137:
81:
58:
361:
1043:
466:
is also unambiguous, and (above all else) is in common usage, and so I think the objection to its use in
Knowledge is somewhat pedantic. --
828:
922:. In addition, I don't like "based on a finite-state-automata concept" in the first sentence. I suggest for the first two sentences: "In
1134:
244:
1053:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
484:
225:
898:
Are you sure DeRemer wrote an LALR parser generator for his 1969 thesis? I can't find a reference to that in the dissertation. --
421:
ightmost derivation in reverse ... The third method, called lookahead LR (LALR for short) ... the LALR parser of Fig. 6.13 ..." --
513:
page that I created for
Knowledge. Afterall, an LALR parser is not concerned with the computation of LALR(1) look-ahead sets.
545:
317:
409:
Hmmm. Looking at an old copy of the Dragon Book (which I've heard is pretty well respected in the field, but I may be wrong):
1133:
I've always heard it pronounced "laller" rather than "el-ay-el-ar" but it is hard to get a reference for this either way.
1118:
282:
163:
33:
670:
Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.
570:
Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.
738:
292:
206:
509:
About the detailed discussion of the LALR parser table construction algorithms ... I think that should belong to the
694:
327:
89:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
737:
I almost just redirected it, given that it's at the very least a valid alternative title and currently largely a
354:
1074:
to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
832:
1138:
1034:
https://web.archive.org/web/20100804231352/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht
1109:
1025:
1021:
782:
654:
1044:
https://web.archive.org/web/20100723153301/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht
1093:
If you have discovered URLs which were erroneously considered dead by the bot, you can report them with
1081:
998:
869:
686:
602:
517:
any erroneous reductions). However, an SLR parser algorithm is the same as an LALR parser algorithm.
510:
496:
263:
39:
1024:. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit
955:
605:. Once fully developed, these two articles are certain to have more similarities than differences. --
800:
all identical pieces of software differing only in the edges in their automata, and those differences
1037:
943:
939:
586:
533:
21:
975:
541:
951:
1047:
947:
884:
474:
1078:
before doing mass systematic removals. This message is updated dynamically through the template
1094:
993:(i.e. why would I be interested in this), then get to the technical stuff in a later paragraph.
903:
810:
778:
746:
650:
634:
610:
481:
182:
994:
923:
888:
865:
234:
86:
1101:
769:
state, not topic or potential state) explains little difference, then there is an argument
582:
677:
From my talk page. As the merge was rejected, the generator article has no been prodded.
1060:, "External links modified" talk page sections are no longer generated or monitored by
971:
919:
622:
537:
524:
308:
150:
1100:
If you found an error with any archives or the URLs themselves, you can fix them with
521:
So I don't think
Knowledge should say that LALR is not good for C++ type languages.
173:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
1150:
899:
806:
742:
630:
606:
467:
724:
402:((This is rubbish, I will try to write something at the weekend (2001-08-18). --
1067:
1017:
883:
was very likely involved in the coding of that generator (written in XPL) also.
848:
598:
456:
431:
1066:. No special action is required regarding these talk page notices, other than
836:
935:
843:
452:
215:
73:
52:
460:
445:
439:
403:
965:
Please make the introductory explanation of LALR parser....introductory
488:
413:"These parsers are called LR parsers because they scan the input from
777:
The literature on these is vast, and there is no issue of sourcing.
451:
OK, I looked at my Dragon Book (2nd ed, BTW) and wrote the articles
1142:
1123:
1002:
979:
959:
907:
892:
873:
852:
814:
786:
750:
658:
638:
614:
590:
549:
499:
473:
Your source material link (to an Oberlin CS lecture) is dead. :( --
1038:
http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht
666:
The above discussion is preserved as an archive of the proposal.
791:
Andy, you're splitting hairs. LALR parsers most definitely do
492:
1048:
http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht
291:
Find pictures for the biographies of computer scientists (see
15:
1028:
for additional information. I made the following changes:
720:
716:
712:
985:
Not a bad idea. Somehow describe what an LALR parser
564:
The following is a closed discussion of the proposal.
444:
Well, I guess my definition was not TOTAL RUBBISH, as
629:
I think the parser generator can be a section here.
85:, a collaborative effort to improve the coverage of
1070:using the archive tool instructions below. Editors
197:Computer science articles needing expert attention
1056:This message was posted before February 2018.
337:WikiProject Computer science/Unreferenced BLPs
8:
621:people will be more confused than ever. --
254:Computer science articles without infoboxes
192:Computer science articles needing attention
158:Here are some tasks awaiting attention:
132:
47:
1162:High-importance Computer science articles
1016:I have just modified 2 external links on
399:Talk moved; was originally on head page.
49:
19:
99:Knowledge:WikiProject Computer science
1167:WikiProject Computer science articles
597:There's no need to have one page for
102:Template:WikiProject Computer science
7:
731:
489:http://www.devincook.com/goldparser/
79:This article is within the scope of
38:It is of interest to the following
273:Timeline of computing 2020–present
14:
1157:B-Class Computer science articles
1020:. Please take a moment to review
842:The number in parenthesis is the
299:Computing articles needing images
946:used in the LALR parsers is the
732:Talk:LALR parser#Merger proposal
149:
72:
51:
20:
575:The result of the proposal was
119:This article has been rated as
1:
1143:01:43, 10 February 2019 (UTC)
1124:07:35, 14 December 2017 (UTC)
1003:13:53, 26 February 2012 (UTC)
980:13:16, 26 February 2012 (UTC)
837:15:10, 24 December 2010 (UTC)
615:02:39, 23 February 2010 (UTC)
591:14:05, 24 November 2011 (UTC)
550:22:12, 9 September 2009 (UTC)
423:Principles of Compiler Design
417:eft-to-right and construct a
353:Tag all relevant articles in
93:and see a list of open tasks.
960:12:18, 2 February 2012 (UTC)
500:21:26, 7 February 2007 (UTC)
493:http://www.parsifalsoft.com/
362:WikiProject Computer science
138:WikiProject Computer science
82:WikiProject Computer science
914:PDA is not a data structure
874:19:26, 6 October 2011 (UTC)
659:00:10, 23 August 2011 (UTC)
293:List of computer scientists
1183:
1087:(last update: 5 June 2024)
1013:Hello fellow Wikipedians,
908:01:15, 2 August 2014 (UTC)
815:01:11, 2 August 2014 (UTC)
771:on that narrow basis alone
477:11:31, Jan 30, 2006 (UTC)
470:16:33, Sep 17, 2004 (UTC)
125:project's importance scale
853:12:50, 8 March 2011 (UTC)
787:15:26, 29 June 2012 (UTC)
751:14:17, 29 June 2012 (UTC)
639:12:27, 8 March 2011 (UTC)
355:Category:Computer science
131:
118:
105:Computer science articles
67:
46:
822:
668:Please do not modify it.
567:Please do not modify it.
455:(which was longish) and
357:and sub-categories with
1129:Pronunciation of "LALR"
1009:External links modified
893:04:18, 9 May 2012 (UTC)
511:LALR parser gernerator
318:Computer science stubs
28:This article is rated
940:Finite-state machines
687:LALR parser generator
603:LALR parser generator
577:no consensus to merge
1068:regular verification
989:rather than what it
944:Model of computation
932:look-ahead LR parser
136:Things you can help
1058:After February 2018
1112:InternetArchiveBot
1063:InternetArchiveBot
948:pushdown automaton
680:The time has come.
34:content assessment
1088:
739:duplicate article
553:
536:comment added by
392:
391:
388:
387:
384:
383:
380:
379:
376:
375:
1174:
1122:
1113:
1086:
1085:
1064:
924:computer science
728:
710:
601:and another for
569:
552:
530:
425:, Aho and Ullman
395:Initial comments
366:
360:
235:Computer science
164:Article requests
153:
146:
145:
133:
107:
106:
103:
100:
97:
96:Computer science
87:Computer science
76:
69:
68:
63:
59:Computer science
55:
48:
31:
25:
24:
16:
1182:
1181:
1177:
1176:
1175:
1173:
1172:
1171:
1147:
1146:
1131:
1116:
1111:
1079:
1072:have permission
1062:
1026:this simple FaQ
1011:
967:
934:) is a type of
916:
861:
825:
823:What's LALR(1)?
767:current article
701:
685:
674:
565:
559:
557:Merger proposal
531:
397:
372:
369:
364:
358:
346:Project-related
341:
322:
303:
277:
258:
239:
220:
201:
177:
121:High-importance
104:
101:
98:
95:
94:
62:High‑importance
61:
32:on Knowledge's
29:
12:
11:
5:
1180:
1178:
1170:
1169:
1164:
1159:
1149:
1148:
1130:
1127:
1106:
1105:
1098:
1051:
1050:
1042:Added archive
1040:
1032:Added archive
1010:
1007:
1006:
1005:
966:
963:
920:data structure
915:
912:
911:
910:
860:
857:
856:
855:
829:89.217.239.233
824:
821:
820:
819:
818:
817:
775:
762:
735:
734:
729:
682:
681:
678:
673:
672:
662:
661:
642:
641:
626:
625:
596:
594:
580:
573:
572:
560:
558:
555:
528:
503:
436:
427:
426:
396:
393:
390:
389:
386:
385:
382:
381:
378:
377:
374:
373:
371:
370:
368:
367:
350:
342:
340:
339:
333:
323:
321:
320:
314:
304:
302:
301:
296:
288:
278:
276:
275:
269:
259:
257:
256:
250:
240:
238:
237:
231:
221:
219:
218:
212:
202:
200:
199:
194:
188:
178:
176:
175:
169:
157:
155:
154:
142:
141:
129:
128:
117:
111:
110:
108:
91:the discussion
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
1179:
1168:
1165:
1163:
1160:
1158:
1155:
1154:
1152:
1145:
1144:
1140:
1136:
1135:198.91.146.14
1128:
1126:
1125:
1120:
1115:
1114:
1103:
1099:
1096:
1092:
1091:
1090:
1083:
1077:
1073:
1069:
1065:
1059:
1054:
1049:
1045:
1041:
1039:
1035:
1031:
1030:
1029:
1027:
1023:
1019:
1014:
1008:
1004:
1000:
996:
992:
988:
984:
983:
982:
981:
977:
973:
964:
962:
961:
957:
953:
949:
945:
941:
937:
933:
929:
925:
921:
918:PDA is not a
913:
909:
905:
901:
897:
896:
895:
894:
890:
886:
880:
876:
875:
871:
867:
858:
854:
851:
850:
845:
841:
840:
839:
838:
834:
830:
816:
812:
808:
803:
798:
794:
790:
789:
788:
784:
780:
776:
772:
768:
763:
759:
755:
754:
753:
752:
748:
744:
740:
733:
730:
726:
722:
718:
714:
709:
705:
700:
696:
692:
688:
684:
683:
679:
676:
675:
671:
669:
664:
663:
660:
656:
652:
647:
644:
643:
640:
636:
632:
628:
627:
624:
619:
618:
617:
616:
612:
608:
604:
600:
593:
592:
588:
584:
578:
571:
568:
562:
561:
556:
554:
551:
547:
543:
539:
535:
527:
526:
522:
518:
514:
512:
507:
502:
501:
498:
497:12.110.196.19
494:
490:
486:
485:0-201-40353-6
483:
478:
476:
475:utopianheaven
471:
469:
463:
462:
458:
454:
449:
447:
442:
441:
434:
433:
424:
420:
416:
412:
411:
410:
407:
405:
400:
394:
363:
356:
352:
351:
349:
347:
343:
338:
335:
334:
332:
330:
329:
324:
319:
316:
315:
313:
311:
310:
305:
300:
297:
294:
290:
289:
287:
285:
284:
279:
274:
271:
270:
268:
266:
265:
260:
255:
252:
251:
249:
247:
246:
241:
236:
233:
232:
230:
228:
227:
222:
217:
214:
213:
211:
209:
208:
203:
198:
195:
193:
190:
189:
187:
185:
184:
179:
174:
171:
170:
168:
166:
165:
160:
159:
156:
152:
148:
147:
144:
143:
139:
135:
134:
130:
126:
122:
116:
113:
112:
109:
92:
88:
84:
83:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
1132:
1110:
1107:
1082:source check
1061:
1055:
1052:
1015:
1012:
990:
986:
968:
931:
927:
917:
881:
877:
862:
847:
826:
801:
796:
792:
779:Andy Dingley
770:
766:
757:
736:
667:
665:
651:Andy Dingley
645:
595:
576:
574:
566:
563:
529:
523:
519:
515:
508:
504:
479:
472:
464:
450:
443:
435:
428:
422:
418:
414:
408:
401:
398:
345:
344:
328:Unreferenced
326:
325:
307:
306:
281:
280:
262:
261:
243:
242:
224:
223:
205:
204:
181:
180:
162:
161:
120:
80:
40:WikiProjects
1018:LALR parser
995:Peter Flass
942:(FSM). The
928:LALR parser
866:Peter Flass
623:Paul B Mann
599:LALR parser
532:—Preceding
525:Paul B Mann
457:LALR parser
1151:Categories
1119:Report bug
761:incorrect.
583:Yellowdesk
1102:this tool
1095:this tool
972:ReveurGAM
950:(PDA)."
938:based on
936:LR parser
859:Earliest?
844:lookahead
538:Paulbmann
453:LR parser
216:Computing
1108:Cheers.—
756:This is
546:contribs
534:unsigned
264:Maintain
207:Copyedit
1022:my edit
952:Ginandi
900:Doradus
807:Doradus
743:Uncle G
704:protect
699:history
631:Sae1962
607:Doradus
468:Doradus
245:Infobox
183:Cleanup
123:on the
30:B-class
885:DBSand
849:Allen3
708:delete
646:Oppose
495:, etc.
226:Expand
36:scale.
926:, an
774:such.
725:views
717:watch
713:links
309:Stubs
283:Photo
140:with:
1139:talk
999:talk
987:does
976:talk
956:talk
930:(or
904:talk
889:talk
870:talk
846:. --
833:talk
811:talk
783:talk
747:talk
721:logs
695:talk
691:edit
655:talk
635:talk
611:talk
587:talk
542:talk
482:ISBN
115:High
1076:RfC
1046:to
1036:to
802:all
797:not
793:not
758:not
461:drj
446:drj
440:drj
432:loh
404:drj
1153::
1141:)
1089:.
1084:}}
1080:{{
1001:)
991:is
978:)
958:)
906:)
891:)
872:)
835:)
813:)
805:--
785:)
749:)
723:|
719:|
715:|
711:|
706:|
702:|
697:|
693:|
657:)
637:)
613:)
589:)
581:--
579:.
548:)
544:•
491:,
438:--
430:--
365:}}
359:{{
1137:(
1121:)
1117:(
1104:.
1097:.
997:(
974:(
954:(
902:(
887:(
868:(
831:(
809:(
781:(
745:(
727:)
689:(
653:(
633:(
609:(
585:(
540:(
419:r
415:l
348::
331::
312::
295:)
286::
267::
248::
229::
210::
186::
167::
127:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
