قواعد النحو المتجاورة للشجرة

قواعد الربط الشجري ( TAG ) هي شكلية نحوية وضعها أرافيند جوشي . تشبه قواعد الربط الشجري إلى حد ما قواعد اللغة الخالية من السياق ، لكن الوحدة الأساسية لإعادة الكتابة هي الشجرة نفسها وليس الرمز. فبينما تحتوي قواعد اللغة الخالية من السياق على قواعد لإعادة كتابة الرموز كسلاسل من رموز أخرى، تحتوي قواعد الربط الشجري على قواعد لإعادة كتابة عقد الأشجار كأشجار أخرى (انظر الشجرة (نظرية الرسم البياني) والشجرة (بنية البيانات) ).

نشأت نظرية TAG من دراسات أجراها جوشي وطلابه حول عائلة قواعد الإضافة (AG)، ^{[ 1 ]} و"قواعد السلاسل" لزيليج هاريس . ^{[ 2 ]} تتعامل قواعد الإضافة مع الخصائص الخارجية للغة بطريقة طبيعية وفعالة، لكنها لا تُقدم توصيفًا جيدًا للبنى الداخلية ؛ والعكس صحيح بالنسبة لقواعد إعادة الكتابة ، أو قواعد بنية العبارة (PSG). في عام 1969، قدم جوشي عائلة من القواعد تستغل هذا التكامل من خلال دمج نوعي القواعد. يكفي عدد قليل جدًا من قواعد إعادة الكتابة البسيطة لتوليد مفردات السلاسل لقواعد الإضافة. تختلف هذه العائلة عن التسلسل الهرمي لتشومسكي-شوتزنبرجر ، لكنها تتقاطع معه بطرق مثيرة للاهتمام وذات صلة لغوية. ^{[ 3 ]} يمكن أيضًا توليد السلاسل المركزية وسلاسل الإضافة بواسطة قواعد التبعية ، مما يُجنّب قيود أنظمة إعادة الكتابة تمامًا. ^{[ 4 ] [ 5 ]}

يمكن تعريف الوسم (TAG) على أنه مجموعة من 5 عناصر${\displaystyle \langle \Sigma ,NT,I,A,S\rangle }$مع: ^{[ 6 ]}

• ${\displaystyle \Sigma }$باعتبارها المجموعة المحدودة من الرموز الطرفية ؛
• ${\displaystyle NT}$باعتبارها المجموعة المحدودة من الرموز غير الطرفية، منفصلة عن${\displaystyle \Sigma }$؛
• ${\displaystyle I}$كمجموعة محدودة من الأشجار المحدودة تسمى الأشجار الأولية ؛
  • تحتوي الأشجار الأولية على عقد داخلية غير طرفية. يمكن أن تتكون الحدود من عقد طرفية وغير طرفية. يتم تمييز العقد غير الطرفية عند الحدود للاستبدال (عادةً بإضافة الرمز '${\displaystyle \downarrow }$(بعد الرمز غير الطرفي). لا يمكن ضم العقد المحددة للاستبدال.
• ${\displaystyle A}$كمجموعة محدودة من الأشجار المحدودة تسمى الأشجار المساعدة ؛
  • تحتوي الأشجار المساعدة على عقدة ورقية خاصة تُعرف باسم عقدة القدم (عادةً ما يتم تمييزها بـ "${\displaystyle \ast }$يجب أن يحمل كل عقدة غير طرفية نفس الرمز غير الطرفي لجذر الشجرة. لا يمكن استبدال العقد السفلية؛ جميع العقد غير الطرفية الأخرى على الحدود مُعلَّمة للاستبدال. وكما هو الحال في الأشجار الأولية، تحمل العقد الداخلية رموزًا غير طرفية.
• ${\displaystyle S}$كرمز بداية خاص، ينتمي إلى مجموعة الرموز غير الطرفية.

بالإضافة إلى ذلك، تم إدخال مجموعات الأشجار المساعدة (TAGs) التي تتضمن قيودًا على الضم على العقد. يمكن لقيد الضم على عقدة ما أن: يمنع الضم تمامًا (NA، للضم الصفري )؛ أو يجعله إلزاميًا (OA)؛ أو يسمح فقط لأشجار مساعدة مختارة بالضم (SA). ^{[ 6 ]}

يوجد نوعان من الأشجار الأساسية في TAG - الأشجار الأولية (يُشار إليها غالبًا بـ '${\displaystyle \alpha }$') والأشجار المساعدة ('${\displaystyle \beta }$تُسمى هذه الأشجار مجتمعة بالأشجار الأولية. تمثل الأشجار الأولية علاقات التكافؤ الأساسية، بينما تسمح الأشجار المساعدة بالتكرار. ^{[ 7 ]}

تبدأ عملية الاشتقاق بشجرة أولية، تُدمج مع أشجار أخرى إما عن طريق الاستبدال أو الإضافة. يستبدل الاستبدال عقدة حدودية بشجرة أولية يكون لجذرها نفس تسمية الورقة التي استُبدلت بها. تُضيف الإضافة شجرة مساعدة - إما عند عقدة حدودية أو داخلية - بحيث تتطابق تسميات جذرها وقاعدتها مع تسمية العقدة المجاورة لها. وبالتالي، يمكن أن تؤدي الإضافة إلى إدخال شجرة مساعدة في مركز شجرة أخرى، ويمكن تطبيق هذه العملية بشكل متكرر. ^{[ 4 ]}

لكل قواعد نحوية خالية من السياق ، يمكن توليد قواعد نحوية مجاورة للشجرة تقبل نفس لغة السلاسل النصية. وبالتالي، يمكن لقواعد النحو المجاورة للشجرة توليد جميع اللغات الخالية من السياق ؛ ^{[ 8 ]} كما يمكنها توليد بعض اللغات الحساسة للسياق ، ولكن ليس جميعها .

مثالان على اللغات الحساسة للسياق / غير الخالية من السياق التي يمكن أن تولدها TAGs (مع قيود الإضافة) هما: ^{[ 8 ]}

• لغة النسخ (أي لغة المربعات )، التي يتم فيها تكرار سلسلة عشوائية:${\displaystyle \left\{ww\mid w\in \Sigma ^{*}\right\}}$

  

• لغة العد الرباعي:${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|1\leq n\}}$

  

تعتبر القواعد النحوية المجاورة للشجرة أكثر قوة (من حيث القدرة التوليدية الضعيفة ) من القواعد النحوية الخالية من السياق، ولكنها أقل قوة من أنظمة إعادة الكتابة الخطية الخالية من السياق ، ^{[ 9 ]} المفهرسة ، ^{[ ملاحظة 1 ]} أو القواعد النحوية الحساسة للسياق .

مثالان على اللغات الحساسة للسياق التي لا تستطيع علامات TAG توليدها هما: ^{[ 8 ]}

• لغة السلاسل الثلاثية (أي لغة المكعبات ):${\displaystyle \left\{www\mid w\in \Sigma ^{*}\right\}}$
• اللغات التي تحتوي على أكثر من أربعة سلاسل أحرف مميزة متساوية الطول؛ على سبيل المثال، لغة العد-5:${\displaystyle \{a^{n}b^{n}c^{n}d^{n}f^{n}|1\leq n\}}$

يمكن تمثيل معالجة اللغات التي يمكن أن تولدها علامات TAG بواسطة آلة دفع مضمنة .

غالباً ما توصف قواعد النحو المتجاورة الشجرية بأنها حساسة للسياق بشكل طفيف . ويُفترض أن هذه الفئات من القواعد النحوية قوية بما يكفي لنمذجة اللغات الطبيعية مع الحفاظ على قابليتها للتحليل بكفاءة في الحالة العامة. ^{[ 8 ]}

قواعد النحو المتجاورة الشجرية المعجمية (LTAG) هي نوع من قواعد النحو المتجاورة الشجرية (TAG)، حيث ترتبط كل شجرة ابتدائية (أولية أو مساعدة) بكلمة معجمية. تحتوي كل شجرة على عقدة طرفية واحدة على الأقل كعقدة ورقية، تُسمى حينها المرساة (المعجمية) للشجرة. وقد طوّر فريق أبحاث XTAG التابع لمعهد أبحاث العلوم المعرفية في جامعة بنسلفانيا قواعد نحوية معجمية للغة الإنجليزية. ^{[ 5 ]}

تسمح متغيرات أخرى من TAG بالأشجار متعددة المكونات ، والأشجار ذات العقد القدمية المتعددة، والامتدادات الأخرى.

• قواعد السلاسل

• مشروع XTAG ، الذي يستخدم علامة TAG لمعالجة اللغة الطبيعية.
• دليل تعليمي حول TAG
• توثيق SemConst: نظرة عامة سريعة على بناء الجملة والواجهة الدلالية التي تمثل مشكلة ضمن إطار عمل TAG.
• مشروع TuLiPa: بنية تحليل اللغة في توبنغن (TuLiPA) هي بيئة تحليل نحوي (ودلالي) متعددة الأشكال، مصممة بشكل أساسي لقواعد النحو المتجاورة متعددة المكونات مع مجموعات شجرية.
• مجموعة أدوات Metagrammar التي توفر العديد من الأدوات لتحرير وتجميع MetaGrammars في TAGs. كما أنها تشمل تغطية واسعة لـ Metagrammars الفرنسية.
• LLP2 محلل نحوي متجاور معجمي للشجرة يوفر بيئة رسومية سهلة الاستخدام (الصفحة باللغة الفرنسية)