صيغة باكوس نور

صيغة باكوس نور

في علوم الحاسب الآلي،(BNF)صيغة باكوس العادية أو صيغة باكوس نور (هو أسلوب تدوين لقواعد السياق الحر، وكثيرا ما تستخدم لوصف تكوين الجملة من اللغات المستخدمة في الكمبيوتر، مثل لغات البرمجة للكمبيوتر، وأشكال الوثيقة، ومجموعات التعليمات وبروتوكولات الاتصال.. ويطبق في الحالات التي تحتاج إلى وصف دقيق للغة، على سبيل المثال، في مواصفات اللغة الرسمية، في الكتيبات، وفي كتب دراسة نظرية لغة البرمجة. وتستخدم العديد من الملحقات والمتغيرات من التدوين الأصلي؛ البعض يتم تعريفها حرفيا، بما فيها صيغة باكوس نور المطولة (EBNF) صيغة باكوس نور المضافة (ABNF).

التاريخ

فكرة شرح بناء اللغة بإعادة كتابة القواعد يمكن إرجاعها إلى عمل بانيني على الاقل (حوالي القرن 4 ق م)، الذي يستخدمه في وصف بناء الكلمة السنسكريتية—وبالتالي، يقترح البعض لإعادة تسمية BNF لصيغة باكوس بانيني [1] اللغويين الأمريكان مثل ليونارد بلومفيلد وزيليج هاريس أخذت هذه الفكرة خطوة أخرى إلى الأمام من خلال محاولة إضفاء الطابع الرسمي على اللغة ودراستها بمصطلحات وخطوات رسمية أساسية (حوالي 1920-1960) وفي الوقت نفسه، إعادة كتابة القواعد مسلسلة بشكل رسمى، ونظم مجردة قد تم تقديمها ودراستها من قبل علماء الرياضيات مثل أكسل أثيو (في 1914)، واميل بوست في (1920s - 1940s) وآلان تورنغ (1936 (نعوم تشومسكي، تدريس اللغويات لطلاب نظرية المعلومات في معهد ماساتشوستس للتكنولوجيا (MIT)، تجمع بين علم اللغة والرياضيات، من خلال أخذ ما هو أساسي من شكليات ثيو كأساس لوصف بناء الجملة في اللغة الطبيعية، وقدم أيضا تمييزا واضحا بين القواعد التوليدية (تلك من قواعد السياق الحر) وقواعد التحول (1956) [2][3]

[4] اعتمد جون باكوس، وهو مصمم لغة برمجة في آي بي إم، على قواعد تشومسكي التوليدية لوصف بناء الجملة للغة البرمجة الجديدة IAL، المعروفة اليوم باسم[5] 58 ALGOL(1959)، باستخدام تدوين BNF. أدت زيادة تطوير ALGOLإلى 60 ALGOL ؛ في تقريرها عام (1963)، بيتر نور أطلق اسمه صيغة باكوس العادية على تدوين باكوس، وقام بتبسيطها لتقليل مجموعة الأحرف المستخدمة. ومع ذلك، دونالد كنوث جادل في هذا وقال ان BNF ينبغى ان تقرأ كصيغة باكوس نور، لأنها «ليست صيغة عادية بأي معنى»، [6] وخلافا، على سبيل المثال، صيغة تشومسكي العادية.

مقدمة

مواصفات BNF هي مجموعة من قواعد الاشتقاق، تكتب بهذا الشكل

<symbol>: = __expression__ 

حيث أن <symbol>الرمز ليس له نهاية، و__expression__ المصطلح يتكون من واحد أو أكثر من تسلسل الرموز؛ يتم فصل أكثر المتسلسلات بواسطة شريط عمودي، '|'، مما يشير إلى إمكانية الاختيار، وكلها تجري استبدالات ممكنة للرمز على اليسار. الرموز التي لا تظهر على الجانب الأيسر تعتبر نهاية طرفية. ومن ناحية أخرى، الرموز التي تظهر على الجانب الأيسر ليس لها نهاية طرفية ومحاطة دائما بين <>

المثال

فعلى سبيل المثال، النظر في الاحتمال BNF الممكنة لعناوين البريد في الولايات المتحدة: <postal-address> = <name-part> <street-address> <zip-part>

<name-part> = <personal-part> <last-name> <opt-jr-part> <EOL> 
| <personal-part> <name-part> <EOL>

<personal-part> = <first-name> | <initial> "." 

<street-address> = <house-num> <street-name> <opt-apt-num> <EOL>

<zip-part> = <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-jr-part> = "Sr." | "Jr." | <roman-numeral> | ""

وهذا يترجم إلى اللغة الإنجليزية على النحو التالي: • عنوان بريدي يتكون من جزء- اسم، يليه جزء-عنوان الشارع، يليه جزء-الرقم البريدي. • جزء-الاسم يتكون من إما: جزء- شخصي يليه اسم العائلة متبوعا باختيارملحق (الابن، الأب، أو عدد سلالي) ونهاية الخط، أو الجزء الشخصي يليه جزء الاسم (هذه القاعدة توضح استخدام الاستدعاء الذاتى في BNFs، الذي يغطي حالة الأشخاص الذين يستخدمون الأسماء الأولى والمتوسطة المتعددة و/ أو الأحرف الأولية). • الجزء-الشخصي يتكون من إما الاسم الأول أو احرف أولية تليها نقطة. • عنوان الشارع يتكون من رقم المنزل، يليه اسم الشارع، يعقبه اختيارالشقة المحددة، يعقبه نهاية السطر. • جزء-الرمز البريدي، يتكون من اسم بلدة، تليها فاصلة، متبوعا برمز الدولة، يليه الرقم البريدي يعقبه نهاية سطر واحد. • جزء (opt-jr-)، يتكون من لاحقة، مثل "Sr." الاب،”Jr.” ألابن أو الأرقام -الرومانية، أو سلسلة فارغة (أي شيء.) لاحظ أنه يتم ترك أشياء كثيرة غير محددة هنا (مثل تنسيق الاسم الأول، محدد الشقة، الرمز البريدي، وألارقام الرومانية) هنا غير. إذا لزم الأمر، قد يمكن وصفها باستدام قواعد BNF إضافية.

مزيد من الأمثلة

بناء جملة بصيغة BNF قد تمثل ذاتها ب BNF كما يلي: <syntax> = <rule> | <rule> <syntax>

<rule> = <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" 
<opt-whitespace> <expression> <line-end>
<opt-whitespace> == " " <opt-whitespace> | "" 
<expression> ::= <list> | <list> "|" <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'" 

هذا يفترض أن المساحة البيضاء غير ضرورية للتفسير الصحيح للقاعدة. <EOL>يمثل محدد نهاية الخط المناسب (في ASCII، تحريك الحاملة و/ أو عدد السطور، اعتمادا على نظام التشغيل. <rule-name>و <text> موجودان ليكونا بديلا مع اسم/ التسمية أو النص الحرفي للقاعدة المعلنة، على التوالي. في الولايات المتحدة مثلا عنوان البريدي أعلاه، الكتلة الكاملة المحصورة بين القوسين هي بناء الجملة. كل خط أو خطوط تجميعية غير منقطعة تعتبر قاعدة، على سبيل المثال قاعدة واحدة تبدأ بـ "<name-part> ==". الجزء الآخر من هذه القاعدة (وبصرف النظر عن نهاية سطر) هو مصطلح، والذي يتكون من قائمتين مفصولتان بأنبوب "|". هاتين القائمتين تتكونا من بعض المصطلحات (ثلاثة مصطلحات ومصطلحين، على التوالي). كل مصطلح في هذه القاعدة المحدة هو اسم قاعدة.

المتغيرات

هناك العديد من المتغيرات والملحقات لصيغة BNF، عموما إما من أجل التبسيط والإيجاز، أو لتكييفه مع تطبيق معين. هناك سمة مشتركة واحدة بين العديد من المتغيرات هو استخدام مشغلي تكرار المصطلح العادي مثل * و+. صيغة باكوس نور المطولة (EBNF) هي صيغة مشتركة. في الواقع المثال أعلاه هو ليس صيغة محضة مخترعة لتقرير 60ALGOL وكان تدوين قوس "[]" تم عرضه في سنوات قليلة لاحقة في لغة بى ال وان لآي بي إم ولكن الآن معترف بها عالميا. ABNF و RBNF والملحقات الأخرى تستخدم عادة لوصف بروتوكولات فرقة هندسة الإنترنت (IETF).

قواعد تحليل المصطلح تبنى على ال BNF وترميزات المصطلحات العادية لتكوين فئة بديلة من القواعد الأساسية، والتي هي أساسا تحليلياً بدلا من التوليد الحرفى.

العديد من مواصفات BNF موجودة على الإنترنت اليوم والمراد ان تكون سهلة القراءة للبشر وغير نظامية. وغالبا ما تشمل العديد من قواعد بناء الجملة التالية والملحقات: • العناصر الاختيارية متضمنة بين قوسين معقوفين. على سبيل المثال [<item-x>] • العناصر تتكرر 0 مرة أو أكثرة متضمنة بين أقواس متعرجة أو تتبعها علامة النجمة على سبيل المثال <word> ::= <letter> {<letter>} • العناصر التي تتكررمرة أو أكثر تتبعها '+' • النهايات الطرفية تظهر بنص عريض والتي لا تعتبر نهاية طرفية تظهر بنص عادي بدلا من استخدام النص المائل وأقواس زاوية • الخيارات البديلة في الإنتاج منفصلة بالرمز ‘|’ على سبيل المثال، <alternative-A> | <alternative-B> • عندما تحتاج البنود إلى التجميع تحاط بين قوسين بسيطين

انظر أيضا

(Railroad diagram). برولوغ

• سودوكود A similar concept

برمجيات باستخدامBNF

• ANTLR Another parser generator written in جافا.
• Coco/R Compiler generator accepting an attributed grammar in EBNF
• بيسون جنو GNU version of yacc.
• RPA BNF parser. Online(PHP) demo parsing: JavaScript, XML
• Yacc parser generator (used with Lex pre-processor).

المراجع

تستند هذة المقالة على مواد من قاموس الحوسبة المجاني على الانترنت، وهو ترخيص تحت رخصة جنو للوثائق الحرة.

1. Letter to ACM Commumications by P.Z. Ingerman (1967) quoted in Rao، T.R.N.؛ Kak، Subhash (1998). "The Panini-Backus Form in Syntax of Formal Languages". مؤرشف من الأصل في 01 يناير 2019. اطلع عليه بتاريخ 04/23/2011.
2. Chomsky، Noam (1956). "Three models for the description of language" (PDF). IRE Transactions on Information Theory. ج. 2 ع. 2: 113–124. DOI:10.1109/TIT.1956.1056813. مؤرشف من الأصل (PDF) في 2015-09-23.
3. Chomsky، Noam (1957). بنى نحوية. The Hague: Mouton.
4. Fulton، Scott M., III (20 مارس 2007). "betanews". مؤرشف من الأصل في 2011-01-14. اطلع عليه بتاريخ 2010-08-14. {{استشهاد ويب}}: الوسيط |الفصل= تم تجاهله (مساعدة)
5. Backus، J.W. (1959). "Proceedings of the International Conference on Information Processing". UNESCO: 125–132. {{استشهاد بدورية محكمة}}: الوسيط |الفصل= تم تجاهله (مساعدة)