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

صيغة باكوس نور
في علوم الحاسب الآلي،(BNF)صيغة باكوس العادية أو صيغة باكوس نور (هو أسلوب تدوين لقواعد السياق الحر، وكثيرا ما تستخدم لوصف تكوين الجملة من اللغات المستخدمة في الكمبيوتر، مثل لغات البرمجة للكمبيوتر، وأشكال الوثيقة، ومجموعات التعليمات وبروتوكولات الاتصال.. ويطبق في الحالات التي تحتاج إلى وصف دقيق للغة، على سبيل المثال، في مواصفات اللغة الرسمية، في الكتيبات، وفي كتب دراسة نظرية لغة البرمجة.
وتستخدم العديد من الملحقات والمتغيرات من التدوين الأصلي؛ البعض يتم تعريفها حرفيا، بما فيها صيغة باكوس نور المطولة (EBNF) صيغة باكوس نور المضافة (ABNF).
التاريخ
فكرة شرح بناء اللغة بإعادة كتابة القواعد يمكن إرجاعها إلى عمل بانيني على الاقل (حوالي القرن 4 ق م)، الذي يستخدمه في وصف بناء الكلمة السنسكريتية—وبالتالي، يقترح البعض لإعادة تسمية BNF لصيغة باكوس بانيني اللغويين الأمريكان مثل ليونارد بلومفيلد وزيليج هاريس أخذت هذه الفكرة خطوة أخرى إلى الأمام من خلال محاولة إضفاء الطابع الرسمي على اللغة ودراستها بمصطلحات وخطوات رسمية أساسية (حوالي 1920-1960)
وفي الوقت نفسه، إعادة كتابة القواعد مسلسلة بشكل رسمى، ونظم مجردة قد تم تقديمها ودراستها من قبل علماء الرياضيات مثل أكسل أثيو (في 1914)، واميل بوست في (1920s - 1940s) وآلان تورنغ (1936 (نعوم تشومسكي، تدريس اللغويات لطلاب نظرية المعلومات في معهد ماساتشوستس للتكنولوجيا (MIT)، تجمع بين علم اللغة والرياضيات، من خلال أخذ ما هو أساسي من شكليات ثيو كأساس لوصف بناء الجملة في اللغة الطبيعية، وقدم أيضا تمييزا واضحا بين القواعد التوليدية (تلك من قواعد السياق الحر) وقواعد التحول (1956)
اعتمد جون باكوس، وهو مصمم لغة برمجة في آي بي إم، على قواعد تشومسكي التوليدية لوصف بناء الجملة للغة البرمجة الجديدة IAL، المعروفة اليوم باسم 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).
المراجع
وصلات خارجية
Backus Normal Form vs. Backus-Naur Form explains some of the history of the two names.
BNF and EBNF: What are they and how do they work? by Lars Marius Garshol.
Augmented BNF for Syntax Specifications: ABNF.
Routing BNF: A Syntax Used in Various Protocol Specifications.
Comparison of different variants of BNF
Syntax diagram of EBNF
Generation of syntax diagrams from EBNF
ISO/IEC 14977:1996(E) Information technology - Syntactic metalanguage - Extended BNF, available from ISO or from Marcus Kuhn (the latter is missing the cover page, but is otherwise much cleaner)
نحو اللغة
Algol-60 BNF, the original BNF.
BNF grammars for SQL-92, SQL-99 and SQL-2003, Freely available BNF grammars for إس كيو إل.
BNF Web Club, Freely available BNF grammars for SQL, أيدا (لغة برمجة)، جافا.
BNF Examples and Full Programming Languages, Freely available BNF grammars for programming languages (C, Java, جافا سكريبت، C#، فيجوال بيزك دوت نت، SQL-89), academic languages, file formats (لغة ترميز النص الفائق، لغة الترميز القابلة للامتداد، صفحات الطرز المتراصة) and others (تعبير نمطيs, YACC). These are written in the GOLD Meta-Language, consisting of BNF and Regular Expressions.
Free Programming Language Grammars for Compiler Construction, Freely available BNF/EBNF grammars for C/C++, باسكال (لغة برمجة)، كوبول، أيدا (لغة برمجة)، PL/I.
لغات شكلية
نظرية المترجم