{"id":1040,"date":"2021-04-11T19:59:59","date_gmt":"2021-04-11T17:59:59","guid":{"rendered":"https:\/\/user.phil.hhu.de\/kallmeyer\/?page_id=1040"},"modified":"2021-07-19T18:01:25","modified_gmt":"2021-07-19T16:01:25","slug":"parsing-sommer-2021","status":"publish","type":"page","link":"https:\/\/user.phil.hhu.de\/kallmeyer\/teaching\/parsing-sommer-2021\/","title":{"rendered":"Parsing &#8211; Sommer 2021"},"content":{"rendered":"<h4>Seminar (Laura Kallmeyer)<\/h4>\n<p>Monday 10.30-12.00 and Tuesday 10.30-12.00.<\/p>\n<p>Start: 12.04.2021. Last session: 20.07.2020.<\/p>\n<p>Due to the current situation concerning Corona, the seminar will be taught as an online seminar. More information can be found <a href=\"https:\/\/moodle.phil.hhu.de\/course\/view.php?id=738\">here<\/a> on the Moodle course page.<\/p>\n<h4>Course description<\/h4>\n<p>Parsing is a central task in natural language processing. Its goal is to compute the syntactic structures of sentences. Such a syntactic structure could either be a constituency structure or a dependency structure. The former is in many cases taken to be generated by a context-free grammar (CFG). Consequently, constituency parsing amounts to a) implementing\/inducing a context-free grammar and b) using this grammar for parsing. Dependency parsing, in contrast to this, is mostly grammar-less parsing using machine-learning techniques.<\/p>\n<p>In this course, we will mainly concentrate on step b) of CFG-based constituency parsing. We will revise various symbolic parsing algorithms that yield, given a CFG and an input sentence, the set of all parse trees for this sentence. In the second half of the course, we will move on to probabilistic parsing, covering Viterbi parsing and weighted deductive parsing with A* estimates.<\/p>\n<p>For references see the slides of the individual sessions.<\/p>\n<h4>Schedule and Slides<\/h4>\n<p>(Some of the slides are from previous years.)<\/p>\n<ul>\n<li>12..04.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/04\/parsing-intro.pdf\">Introduction<\/a>&nbsp;<\/li>\n<li>13.04.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-cfg.pdf\">Context-free grammars (CFG)<\/a><\/li>\n<li>19.04.21 CFG continued<\/li>\n<li>20.04.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-pda.pdf\">Push-Down Automata (PDA)<\/a><\/li>\n<li>26.04.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-unger.pdf\">Unger\u2019s Parser<\/a>.<br><a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/ex-unger.pdf\">Example<\/a>&nbsp;of a trace for Unger\u2019s parser.<br>An implementation of Unger\u2019s Parser (by Simon Petitjean) can be found&nbsp;<a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/unger.py\">here<\/a>.<\/li>\n<li>27.04.21&nbsp;<a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-top-down-1.pdf\">Top-down Parsing (LL-Parsing)<\/a>.<\/li>\n<li>03.05.21&nbsp;<a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-deduction.pdf\">Parsing as Deduction<\/a>.<br>An example of agenda-based parsing can be found&nbsp;<a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2019\/04\/deduction-example.pdf\">here<\/a>.<\/li>\n<li>04.05.21 Parsing as Deduction continued.<\/li>\n<li>10.05.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-cyk.pdf\">CYK Parsing<\/a><\/li>\n<li>11.05.21 CYK continued<\/li>\n<li>17.05.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-shift-reduce.pdf\">Shift reduce parsing<\/a>, <a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/ll-k.pdf\">LL(1) Parsing<\/a><\/li>\n<li>18.05.21 LL(1) Parsing continued<\/li>\n<li>24.05.21 f\u00e4llt aus (Pfingsten)<\/li>\n<li>25.05.21&nbsp;<a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/left-corner.pdf\">Left Corner Parsing<\/a><\/li>\n<li>31.05.21 Left Corner Parsing continued<\/li>\n<li>01.06.21 <a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/earley.pdf\">Earley Parsing<\/a><\/li>\n<li>07.06.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/lr.pdf\">LR Parsing<\/a><\/li>\n<li>08.06.21 LR continued<\/li>\n<li>14.06.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-tomita.pdf\">Tomita<\/a><\/li>\n<li>15.06.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2019\/07\/parsing-pcfg.pdf\">PCFG, Inside and outside, Viterbi<\/a><\/li>\n<li>21.06.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-treebank-grammars.pdf\">Treebank grammars&nbsp;<\/a><\/li>\n<li>22.06.21 Treebank grammar continued&nbsp;<\/li>\n<li>28.06.21 <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-weighted-deductive-parsing.pdf\">Weighted deductive parsing<\/a><\/li>\n<li>29.06.21 Weighted deductive parsing continued. See <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2020\/07\/parsing-homework-weighted-deductive.pdf\">here<\/a> for an exercise from last year that extends the Earley deduction rules with weights.<\/li>\n<li>05.07.21 <a href=\"https:\/\/user.phil-fak.uni-duesseldorf.de\/~kallmeyer\/Parsing\/a-star-parsing.pdf\">A* parsing<\/a><\/li>\n<li>06.07.21 Vertretung: Martin Zakrezewski<\/li>\n<li>12.07.21 A* parsing continued. <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/07\/k-best-example.pdf\">Example for k-best parsing<\/a>. And a second example for k-best parsing. a second <a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/07\/k-best-example2.pdf\">example for k-best parsing<\/a><\/li>\n<li>13.07.21 Transition-based neural constituency parsing.&nbsp;&nbsp;Literatur: Sagae and Lavie <a href=\"https:\/\/www.aclweb.org\/anthology\/W05-1513.pdf\">A Classifier-Based Parser with Linear Run-Time Complexity<\/a>, Dyer et al. <a href=\"https:\/\/aclanthology.org\/N16-1024\/\">Recurrent Neural Network Grammars,.<\/a> Liu, and Zhang <a href=\"https:\/\/aclanthology.org\/Q17-1029\/\">In-OrderTransition-based Constituent Parsing<\/a>&nbsp;<\/li>\n<li>19.07.21 Transition-based parsing continued. Hybrid, in H\u00f6rsaal 25.31.HS 5J (24 Corona-Pl\u00e4tze). Details in Moodle.<\/li>\n<li>20.07.21 f\u00e4llt aus.<\/li>\n<\/ul>\n<h4>&nbsp;<\/h4>\n<h4>Homework<\/h4>\n<p>There are weekly exercises for the course. These exercises are obligatory, they have to be handed in via&nbsp;<a href=\"https:\/\/moodle.phil.hhu.de\/course\/view.php?id=738\">Moodle<\/a>. The solutions of the exercises will be discussed in the course.<\/p>\n<ul>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-2021-homework-cfg.pdf\">Homework CFG<\/a>, due 26.04.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-homework-top-down.pdf\">Homework Top-Down Parsing<\/a>, due 03.05.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/05\/parsing-homework-deduction-1.pdf\">Homework Parsing as Deduction<\/a>, due 10.05.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-cyk.pdf\">Homework CYK,&nbsp;<\/a>due 17.05.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-shift-reduce.pdf\">Homework CYK and Shift-reduce, <\/a>due Tuesday 25.05.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-ll1.pdf\">Homework LL(1)<\/a>&nbsp;due Monday 31.05.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-left-corner-earley.pdf\">Homework Left-Corner, Earley<\/a>, due Monday 07.06.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-lr.pdf\">Homework LR Parsing<\/a>, due Monday 14.06.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/06\/parsing-homework-tomita.pdf\">Homework Tomita<\/a>, due Monday 21.06.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/07\/parsing-homework-pcfg.pdf\">Homework PCFG<\/a>, due Monday 28.06.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/07\/parsing-homework-em-weighted-deduction.pdf\">Homework EM and weighted deductive parsing<\/a>, due Monday 05.07.21 (with solution)<\/li>\n<li><a href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-content\/uploads\/sites\/19\/2021\/07\/parsing-homework-astar.pdf\">Homework A* Parsing<\/a>, due Monday 12.07.21<\/li>\n<\/ul>\n\n\n<h4>Homework<\/h4>\n\n\n\n<p>There are weekly exercises for the course. These exercises are obligatory, they have to be handed in via&nbsp;<a href=\"https:\/\/moodle.phil.hhu.de\/course\/view.php?id=738\">Moodle<\/a>. The solutions of the exercises will be discussed in the course.<\/p>\n\n\n\n<h4>Leistungsnachweise<\/h4>\n\n\n\n<p>Sowohl f\u00fcr einen BN als auch f\u00fcr eine AP m\u00fcssen mindestens 9 der 12 Hausaufgabenbl\u00e4tter bearbeitet und sinnvoll gel\u00f6st werden. Gruppenarbeit (max. Gruppengr\u00f6\u00dfe ist 3) ist erlaubt, bitte alle Namen auf die Abgabe.<br>F\u00fcr eine AP kann zus\u00e4tzlich eine individuelle Pr\u00fcfung vereinbart werden, zum Beispiel eine m\u00fcndliche Pr\u00fcfung.<\/p>\n\n\n\n<p>(F\u00fcr Studierende des BA Computerlinguistik integrativ ist Parsing eine Grundveranstaltung in CL5, hier ist keine AP vorgesehen.)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Seminar (Laura Kallmeyer) Monday 10.30-12.00 and Tuesday 10.30-12.00. Start: 12.04.2021. Last session: 20.07.2020. Due to the current situation concerning Corona, the seminar will be taught as an online seminar. More information can be found here on the Moodle course page. <span class=\"excerpt-dots\">&hellip;<\/span> <a class=\"more-link\" href=\"https:\/\/user.phil.hhu.de\/kallmeyer\/teaching\/parsing-sommer-2021\/\"><span class=\"more-msg\">Continue reading &rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"parent":25,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"ngg_post_thumbnail":0},"_links":{"self":[{"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/pages\/1040"}],"collection":[{"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/comments?post=1040"}],"version-history":[{"count":73,"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/pages\/1040\/revisions"}],"predecessor-version":[{"id":1361,"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/pages\/1040\/revisions\/1361"}],"up":[{"embeddable":true,"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/pages\/25"}],"wp:attachment":[{"href":"https:\/\/user.phil.hhu.de\/kallmeyer\/wp-json\/wp\/v2\/media?parent=1040"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}