القواعد الرسمية

جزء من سلسلة عن
اللغات الرسمية
المفاهيم الرئيسية النظام الرسمي الأبجدية بناء الجملة الدلالة (المنطق) الدلالات (لغات البرمجة) القواعد الرسمية قاعدة التشكيل صيغة جيدة التكوين نظرية الأتمتة تعبير منتظم إنتاج تعبير الأرض الصيغة الذرية
التطبيقات الأساليب الرسمية حساب القضايا منطق المسند التدوين الرياضي معالجة اللغة الطبيعية نظرية لغة البرمجة اللغويات الحاسوبية تحليل بناء الجملة التحقق الرسمي إثبات النظريات آليا
ف ت هـ

يصف القواعد النحوية الرسمية السلاسل من أبجدية لغة رسمية والتي تعتبر صالحة وفقًا لقواعد اللغة . لا تصف القواعد النحوية معنى السلاسل أو ما يمكن فعله بها في أي سياق - فقط شكلها. يتم تعريف القواعد النحوية الرسمية على أنها مجموعة من قواعد الإنتاج لمثل هذه السلاسل في لغة رسمية.

نظرية اللغة الرسمية، وهي التخصص الذي يدرس القواعد النحوية واللغات الرسمية، هي فرع من فروع الرياضيات التطبيقية . توجد تطبيقاتها في علوم الكمبيوتر النظرية ، واللغويات النظرية ، والدلالات الرسمية ، والمنطق الرياضي ، وغيرها من المجالات.

القواعد النحوية الرسمية هي مجموعة من القواعد لإعادة كتابة السلاسل، جنبًا إلى جنب مع "رمز البداية" الذي تبدأ منه إعادة الكتابة. لذلك، يُنظر إلى القواعد النحوية عادةً على أنها مولد لغة. ومع ذلك، يمكن استخدامها أحيانًا أيضًا كأساس لـ " المتعرف " - وهي وظيفة في الحوسبة تحدد ما إذا كانت سلسلة معينة تنتمي إلى اللغة أم أنها غير صحيحة نحويًا. لوصف مثل هذه المتعرفات، تستخدم نظرية اللغة الرسمية شكليات منفصلة، ​​تُعرف باسم نظرية الأتمتة . إحدى النتائج المثيرة للاهتمام لنظرية الأتمتة هي أنه من غير الممكن تصميم متعرف لبعض اللغات الرسمية. ^[1] التحليل هو عملية التعرف على لفظ (سلسلة في اللغات الطبيعية) عن طريق تقسيمها إلى مجموعة من الرموز وتحليل كل منها مقابل قواعد اللغة. معظم اللغات لها معاني لفظها المنظمة وفقًا لقواعدها النحوية - وهي ممارسة تُعرف باسم الدلالات التركيبية . ونتيجة لذلك، فإن الخطوة الأولى لوصف معنى الكلام في اللغة هي تقسيمه جزءًا تلو الآخر والنظر إلى شكله المحلل (المعروف باسم شجرة التحليل في علوم الكمبيوتر، وبنيته العميقة في القواعد التوليدية ).

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

على عكس نظام شبه ثو ، والذي يتم تعريفه بالكامل بهذه القواعد، يميز القواعد النحوية أيضًا بين نوعين من الرموز: الرموز غير النهائية والرموز النهائية ؛ يجب أن يحتوي كل جانب أيسر على رمز غير نهائي واحد على الأقل. كما يميز أيضًا رمزًا غير نهائي خاصًا، يسمى رمز البداية .

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

في الأمثلة التالية ، رموز المحطة هي a و b ، ورمز البداية هو S.

لنفترض أن لدينا قواعد الإنتاج التالية:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

ثم نبدأ بـ S ، ويمكننا اختيار قاعدة لتطبيقها عليه. إذا اخترنا القاعدة 1، نحصل على السلسلة aSb . إذا اخترنا القاعدة 1 مرة أخرى، نستبدل S بـ aSb ونحصل على السلسلة aaSbb . إذا اخترنا الآن القاعدة 2، نستبدل S بـ ba ونحصل على السلسلة aababb ، وننتهي. يمكننا كتابة هذه السلسلة من الخيارات بشكل أكثر إيجازًا، باستخدام الرموز: . ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$

لغة القواعد النحوية هي المجموعة اللانهائية ، حيث هي مرات متكررة ( وتمثل على وجه الخصوص عدد المرات التي تم فيها تطبيق قاعدة الإنتاج 1). هذه القواعد النحوية خالية من السياق (تظهر فقط النهايات غير النهائية الفردية على الجانبين الأيسر) ولا لبس فيها. ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaaabbb,\dotsc \}}$${\displaystyle a^{k}}$${\displaystyle أ}$${\displaystyle k}$${\displaystyle n}$

افترض أن القواعد هي هذه بدلاً من ذلك:

1.${\displaystyle S\rightarrow a}$

2.${\displaystyle S\rightarrow SS}$

3.${\displaystyle aSa\rightarrow b}$

هذه القواعد النحوية ليست خالية من السياق بسبب القاعدة 3 وهي غامضة بسبب الطرق المتعددة التي يمكن بها استخدام القاعدة 2 لتوليد تسلسلات من s. ${\displaystyle S}$

ومع ذلك، فإن اللغة التي تولدها هي ببساطة مجموعة من جميع السلاسل غير الفارغة المكونة من s و/أو s. من السهل ملاحظة ذلك: لتوليد a من an ، استخدم القاعدة 2 مرتين لتوليد ، ثم القاعدة 1 مرتين والقاعدة 3 مرة واحدة لإنتاج . وهذا يعني أنه يمكننا توليد تسلسلات غير فارغة عشوائية من s ثم استبدال كل منها بـ أو كما يحلو لنا. ${\displaystyle أ}$${\displaystyle b}$${\displaystyle b}$${\displaystyle S}$${\displaystyle SSS}$${\displaystyle b}$${\displaystyle S}$${\displaystyle أ}$${\displaystyle b}$

يمكن إنشاء نفس اللغة بشكل بديل من خلال قواعد نحوية غير غامضة وخالية من السياق؛ على سبيل المثال، القواعد النحوية العادية مع القواعد

1.${\displaystyle S\rightarrow aS}$

2.${\displaystyle S\rightarrow bS}$

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

في الصيغة الكلاسيكية للقواعد التوليدية التي اقترحها لأول مرة نعوم تشومسكي في الخمسينيات من القرن العشرين، ^{[2] [3]} تتكون القواعد التوليدية من المكونات التالية:

• مجموعة منتهية N من الرموز غير النهائية ، والتي لا تترابط مع السلاسل المكونة من G.
• مجموعة محدودة من الرموز الطرفية المنفصلة عن N.${\displaystyle \سيجما }$
• مجموعة منتهية P من قواعد الإنتاج ، كل قاعدة من النموذج

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

حيث هو عامل نجمة كلين و يدل على اتحاد المجموعة . أي أن كل قاعدة إنتاج ترسم من سلسلة من الرموز إلى أخرى، حيث تحتوي السلسلة الأولى ("الرأس") على عدد عشوائي من الرموز بشرط أن يكون أحدها على الأقل غير طرفي. في حالة أن السلسلة الثانية ("الجسم") تتكون فقط من السلسلة الفارغة - أي أنها لا تحتوي على أي رموز على الإطلاق - فيمكن الإشارة إليها باستخدام تدوين خاص (غالبًا ، e أو ) لتجنب الارتباك. تسمى هذه القاعدة قاعدة محو .${\displaystyle {*}}$${\displaystyle \cup }$${\displaystyle \لامدا }$${\displaystyle \epsilon }$

• رمز مميز وهو رمز البداية ، ويسمى أيضًا رمز الجملة .${\displaystyle S\in N}$

يتم تعريف القواعد النحوية رسميًا على أنها مجموعة من الجمل . غالبًا ما يُطلق على مثل هذه القواعد النحوية الرسمية اسم نظام إعادة الكتابة أو قواعد بنية العبارة في الأدبيات. ^{[4] [5]}${\displaystyle (N,\Sigma ,P,S)}$

يمكن تعريف عملية القواعد النحوية من حيث العلاقات الموجودة على السلاسل:

• بالنظر إلى القواعد النحوية ، فإن العلاقة الثنائية (التي تنطق "G مشتقة في خطوة واحدة") على السلاسل في يتم تعريفها بواسطة: ${\displaystyle G=(N,\Sigma ,P,S)}$${\displaystyle {\underset {G}{\Rightarrow }}}$${\displaystyle (\Sigma \cup N)^{*}}$

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• العلاقة (التي تنطق G مشتقة من صفر أو أكثر من الخطوات ) يتم تعريفها على أنها الإغلاق المتعدي الانعكاسي لـ${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$${\displaystyle {\underset {G}{\Rightarrow }}}$
• أالشكل الجملي هو أحد أعضاء ذلك الذي يمكن اشتقاقه في عدد محدود من الخطوات من رمز البداية ؛ أي أن الشكل الجملي هو أحد أعضاء . الشكل الجملي الذي لا يحتوي على أي رموز غير نهائية (أي أنه أحد أعضاء ) يسمى جملة . ^[6]${\displaystyle (\Sigma \cup N)^{*}}$${\displaystyle S}$${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$${\displaystyle \سيجما ^{*}}$
• لغة ، والتي يشار إليها بـ ، يتم تعريفها على أنها مجموعة الجمل التي بناها .${\displaystyle G}$${\displaystyle {\boldsymbol {L}}(G)}$${\displaystyle G}$

القواعد النحوية هي في الواقع نظام نصف ثو ، حيث تعيد كتابة السلاسل بنفس الطريقة تمامًا؛ والفرق الوحيد هو أننا نميز بين رموز غير نهائية محددة ، والتي يجب إعادة كتابتها في قواعد إعادة الكتابة، ولا تهتم إلا بإعادة الكتابة من رمز البداية المحدد إلى السلاسل بدون رموز غير نهائية. ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle (N\cup \Sigma ,P)}$${\displaystyle S}$

بالنسبة لهذه الأمثلة، يتم تحديد اللغات الرسمية باستخدام تدوين بناء المجموعة .

خذ بعين الاعتبار القواعد النحوية حيث أن ، ، هو رمز البداية، ويتكون من قواعد الإنتاج التالية: ${\displaystyle G}$${\displaystyle N=\left\{S,B\right\}}$${\displaystyle \Sigma =\left\{a,b,c\right\}}$${\displaystyle S}$${\displaystyle P}$

1.${\displaystyle S\rightarrow aBSc}$

2.${\displaystyle S\rightarrow abc}$

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

تحدد هذه القواعد النحوية اللغة حيث يشير إلى سلسلة من n متتالية من علامات "s". وبالتالي، فإن اللغة هي مجموعة السلاسل التي تتكون من علامة "s" واحدة أو أكثر، متبوعة بنفس العدد من علامات "s"، متبوعة بنفس العدد من علامات "s". ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle a^{n}}$${\displaystyle أ}$${\displaystyle أ}$${\displaystyle b}$${\displaystyle c}$

بعض الأمثلة على اشتقاق السلاسل في : ${\displaystyle L(G)}$

(في التدوين: يقرأ "السلسلة P تولد السلسلة Q عن طريق إنتاج i "، ويتم الإشارة إلى الجزء الناتج في كل مرة بخط غامق.)${\displaystyle P{\underset {i}{\Rightarrow }}Q}$

عندما صاغ نعوم تشومسكي لأول مرة القواعد النحوية التوليدية في عام 1956، ^[2] صنفها إلى أنواع تُعرف الآن باسم هرم تشومسكي . والفرق بين هذه الأنواع هو أن لديها قواعد إنتاج صارمة بشكل متزايد وبالتالي يمكنها التعبير عن عدد أقل من اللغات الرسمية. هناك نوعان مهمان هما القواعد النحوية الخالية من السياق (النوع 2) والقواعد النحوية العادية (النوع 3). تُسمى اللغات التي يمكن وصفها بمثل هذه القواعد النحوية باللغات الخالية من السياق واللغات العادية ، على التوالي. وعلى الرغم من أنها أقل قوة بكثير من القواعد النحوية غير المقيدة (النوع 0)، والتي يمكنها في الواقع التعبير عن أي لغة يمكن قبولها بواسطة آلة تورينج ، إلا أن هذين النوعين المقيدان من القواعد النحوية غالبًا ما يتم استخدامهما لأنه يمكن تنفيذ المحللات الخاصة بهما بكفاءة. ^[7] على سبيل المثال، يمكن التعرف على جميع اللغات العادية بواسطة آلة الحالة المحدودة ، وبالنسبة للمجموعات الفرعية المفيدة من القواعد النحوية الخالية من السياق، توجد خوارزميات معروفة لتوليد محللات LL فعالة ومحللات LR للتعرف على اللغات المقابلة التي تولدها هذه القواعد النحوية.

القواعد النحوية الخالية من السياق هي قواعد نحوية يتكون الجانب الأيسر لكل قاعدة إنتاج فيها من رمز غير نهائي واحد فقط. هذا القيد ليس تافهًا؛ فلا يمكن إنشاء كل اللغات باستخدام القواعد النحوية الخالية من السياق. تسمى تلك التي يمكن إنشاؤها باللغات الخالية من السياق .

اللغة المحددة أعلاه ليست لغة خالية من السياق، ويمكن إثبات ذلك بدقة باستخدام مبرهنة الضخ للغات الخالية من السياق ، ولكن على سبيل المثال، اللغة (1 على الأقل متبوعة بنفس عدد "s") خالية من السياق، حيث يمكن تعريفها من خلال القواعد النحوية باستخدام ، ، رمز البداية، وقواعد الإنتاج التالية: ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{2}}$${\displaystyle N=\left\{S\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ab}$

يمكن التعرف على لغة خالية من السياق في الوقت المناسب ( انظر تدوين Big O ) بواسطة خوارزمية مثل مُتعرف Earley . أي أنه بالنسبة لكل لغة خالية من السياق، يمكن بناء آلة تأخذ سلسلة كمدخل وتحدد في الوقت المناسب ما إذا كانت السلسلة عضوًا في اللغة، حيث هو طول السلسلة. ^[8] اللغات الخالية من السياق الحتمية هي مجموعة فرعية من اللغات الخالية من السياق والتي يمكن التعرف عليها في وقت خطي. ^[9] توجد خوارزميات مختلفة تستهدف إما هذه المجموعة من اللغات أو بعض المجموعات الفرعية منها. ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3})}$${\displaystyle n}$

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

اللغة المحددة أعلاه ليست منتظمة، ولكن اللغة (1 على الأقل متبوعة بـ 1 على الأقل ، حيث قد تكون الأرقام مختلفة) منتظمة، كما يمكن تعريفها من خلال القواعد النحوية باستخدام ، ، رمز البداية، وقواعد الإنتاج التالية: ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{3}}$${\displaystyle N=\left\{S,A,B\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

يمكن التعرف على جميع اللغات التي تم إنشاؤها بواسطة قواعد نحوية منتظمة في الوقت المناسب بواسطة آلة الحالة المحدودة. وعلى الرغم من أنه في الممارسة العملية، يتم التعبير عن القواعد النحوية المنتظمة عادةً باستخدام التعبيرات المنتظمة ، إلا أن بعض أشكال التعبير المنتظم المستخدمة في الممارسة العملية لا تولد اللغات المنتظمة بدقة ولا تظهر أداءً تعرفيًا خطيًا بسبب هذه الانحرافات. ${\displaystyle O(n)}$

لقد تم تطوير العديد من التوسعات والاختلافات في التسلسل الهرمي الأصلي لقواعد النحو الرسمية الذي وضعه تشومسكي، سواء من قبل علماء اللغة أو علماء الكمبيوتر، وذلك عادةً إما من أجل زيادة قوتها التعبيرية أو من أجل تسهيل تحليلها أو فهمها. تتضمن بعض أشكال قواعد النحو التي تم تطويرها ما يلي:

• تعمل قواعد النحو المجاورة للأشجار على زيادة قدرة قواعد النحو التوليدية التقليدية على التعبير من خلال السماح لقواعد إعادة الكتابة بالعمل على أشجار التحليل بدلاً من السلاسل فقط. ^[10]
• تسمح قواعد الإلحاق ^[11] وقواعد السمات ^{[12] [13]} بزيادة قواعد إعادة الكتابة باستخدام السمات والعمليات الدلالية، وهي مفيدة لزيادة التعبير النحوي وبناء أدوات ترجمة اللغة العملية.

القواعد النحوية التكرارية هي قواعد نحوية تحتوي على قواعد إنتاجية متكررة . على سبيل المثال، تكون القواعد النحوية للغة خالية من السياق متكررة إلى اليسار إذا كان هناك رمز غير نهائي A يمكن وضعه من خلال قواعد الإنتاج لإنتاج سلسلة مع A كرمز أقصى اليسار. ^[14] مثال على القواعد النحوية التكرارية هو جملة داخل جملة مفصولة بفاصلتين. ^[15] يمكن أن تكون جميع أنواع القواعد النحوية في التسلسل الهرمي تشومسكي متكررة.

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

النهج البديل هو صياغة اللغة من حيث القواعد النحوية التحليلية في المقام الأول، والتي تتوافق بشكل مباشر مع بنية ودلالات المحلل اللغوي للغة. تتضمن أمثلة قواعد النحو التحليلية ما يلي:

• لغة التحليل من أعلى إلى أسفل (TDPL): صيغة نحوية تحليلية بسيطة للغاية تم تطويرها في أوائل سبعينيات القرن العشرين لدراسة سلوك المحللات من أعلى إلى أسفل . ^[16]
• قواعد الارتباط : شكل من أشكال القواعد التحليلية المصممة لعلم اللغة ، والتي تستمد البنية النحوية من خلال فحص العلاقات الموضعية بين أزواج الكلمات. ^{[17] [18]}
• تحليل قواعد التعبير ( PEGs): تعميم أحدث لـ TDPL مصمم حول احتياجات التعبير العملي لكتاب لغة البرمجة والمترجمين . ^[19]