جنو بيسون

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة

برنامج GNU Bison ، المعروف باسم Bison ، هو مولد محلل نحوي جزء من مشروع GNU . يقرأ Bison مواصفات مكتوبة بصيغة Bison (الموصوفة بأنها " صيغة BNF قابلة للقراءة آليًا " [ 3 ] )، ويحذر من أي غموض في التحليل ، ثم يُنشئ محللًا نحويًا يقرأ سلاسل من الرموز ويحدد ما إذا كانت السلسلة تتوافق مع الصيغة النحوية المحددة في القواعد.

تتميز المحللات المُولَّدة بأنها قابلة للنقل: فهي لا تتطلب أي مُجمِّعات مُحدَّدة. يُولِّد برنامج Bison افتراضيًا محللات LALR(1)، ولكنه يستطيع أيضًا توليد محللات LR وIELR(1) و GLR القياسية . [ 4 ]

في وضع POSIX ، يتوافق برنامج Bison مع برنامج Yacc ، ولكنه يحتوي أيضًا على العديد من الإضافات مقارنةً بهذا البرنامج السابق، بما في ذلك

  • توليد أمثلة مضادة للصراعات
  • تتبع الموقع (مثل الملف، السطر، العمود)
  • رسائل خطأ نحوية غنية وقابلة للتدويل في المحللات النحوية المُنشأة
  • توليد أخطاء بناء الجملة القابل للتخصيص،
  • المحللات القابلة لإعادة الدخول
  • قم بدفع المحللات، مع الإكمال التلقائي
  • دعم المراجع المسماة
  • أنواع متعددة من التقارير (رسومية، XML) على المحلل اللغوي المُنشأ
  • يدعم العديد من لغات البرمجة ( C ، C++ ، D ، أو Java )

يُستخدم برنامج Flex ، وهو محلل معجمي تلقائي ، غالبًا مع برنامج Bison، لتقسيم بيانات الإدخال إلى رموز وتزويد Bison بالرموز. [ 5 ]

كتب روبرت كوربيت برنامج Bison في الأصل عام 1985. [ 1 ] وفي وقت لاحق، عام 1989، أصدر روبرت كوربيت مولد محلل لغوي آخر باسم Berkeley Yacc . وقد جعل ريتشارد ستالمان برنامج Bison متوافقًا مع Yacc . [ 6 ]

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

سمات

توليد الأمثلة المضادة

تُعدّ معالجة التعارضات (تعارضات الإزاحة/الاختزال والاختزال/الاختزال) من المسائل الحساسة في مولدات محللات LR. في العديد من مولدات محللات LR، تتطلب معالجة التعارضات تحليلًا لأتمتة المحلل، الأمر الذي يستلزم خبرةً من المستخدم.

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

على سبيل المثال، في قاعدة نحوية تعاني من مشكلة "else" المعلقة سيئة السمعة ، أفاد بايسون

doc/if-then-else.y: تحذير : تعارض في عملية الإزاحة/الاختزال على الرمز المميز "else" [- Wcounterexamples ] مثال: عبارة "if" expr "then" عبارة "if" expr "then" stmt • عبارة "else" stmt اشتقاق الإزاحة if_stmt ↳ "if" expr "then" stmt ↳ if_stmt ↳ "if" expr "then" stmt • "else" stmt مثال: "if" expr "then" "if" expr "then" stmt • "else" stmt تقليل الاشتقاق if_stmt ↳ "if" expr "then" stmt "else" stmt ↳ if_stmt ↳ "if" expr "then" stmt •

إعادة الدخول

إعادة الدخول هي ميزة تمت إضافتها إلى Bison ولا توجد في Yacc.

عادةً، يُنشئ Bison محللاً غير قابل لإعادة الدخول . ولتحقيق إعادة الدخول، يجب استخدام التصريح. يمكن الاطلاع على مزيد من التفاصيل حول إعادة الدخول في Bison في دليل Bison. [ 7 ]%define api.pure

لغات الإخراج

يمكن لبرنامج Bison توليد التعليمات البرمجية للغات C و C++ و D و Java . [ 8 ]

لاستخدام المحلل اللغوي الذي تم إنشاؤه بواسطة Bison من لغات أخرى، يمكن استخدام أداة ربط اللغة مثل SWIG .

ترخيص وتوزيع الكود المُنشأ

لأن برنامج Bison يقوم بإنشاء شفرة مصدرية يتم إضافتها بدورها إلى الشفرة المصدرية لمشاريع برمجية أخرى، فإنه يثير بعض الأسئلة البسيطة ولكن المثيرة للاهتمام حول حقوق النشر.

لا يلزم الحصول على ترخيص متوافق مع رخصة جنو العمومية العامة

يتضمن الكود المُولّد بواسطة Bison كميات كبيرة من الكود من مشروع Bison نفسه. تُوزّع حزمة Bison بموجب شروط رخصة جنو العمومية (GPL)، ولكن أُضيف استثناء بحيث لا تنطبق رخصة جنو العمومية على المُخرجات. [ 9 ] [ 10 ]

نصت الإصدارات السابقة من Bison على أن أجزاء من مخرجاتها مرخصة أيضًا بموجب رخصة GPL، وذلك بسبب تضمين وظيفة yyparse() من الكود المصدري الأصلي في المخرجات.

توزيع الحزم باستخدام Bison

قد يكون أمام مشاريع البرمجيات الحرة التي تستخدم Bison خيار توزيع إما شفرة المصدر التي يُدخلها المشروع إلى Bison، أو شفرة C الناتجة عن Bison. كلا الخيارين كافٍ لتمكين المستلم من تجميع شفرة المصدر للمشروع. مع ذلك، ينطوي توزيع المدخلات فقط على عيب بسيط يتمثل في ضرورة تثبيت نسخة متوافقة من Bison لدى المستلمين ليتمكنوا من توليد شفرة C اللازمة عند تجميع المشروع. أما توزيع شفرة C الناتجة فقط، فيُصعّب على المستلمين تعديل المحلل اللغوي، لأن هذه الشفرة لم تُكتب بواسطة بشر أو للبشر ، بل صُممت لتُدخل مباشرةً إلى مُجمِّع C.

يمكن تجنب هذه المشاكل بتوزيع كلٍ من ملفات الإدخال والشيفرة المُولَّدة. سيستخدم معظم المطورين الشيفرة المُولَّدة في عملية التجميع، تمامًا كما هو الحال مع أي برنامج آخر، ولكن يمكن لأي شخص يرغب في تعديل مُحلِّل الشيفرة تعديل ملفات الإدخال أولًا ثم إعادة توليد الملفات المُولَّدة قبل التجميع. عادةً لا تحتوي أنظمة التحكم في الإصدارات الخاصة بالمشاريع التي تُوزِّع كلا النوعين من الملفات على الملفات المُولَّدة ، إذ تُولَّد هذه الملفات فقط عند إصدار نسخة جديدة.

تتطلب بعض التراخيص، مثل رخصة جنو العمومية (GPL )، أن يكون الكود المصدري بصيغته المُفضلة لإجراء التعديلات عليه . لذا، يجب على المشاريع المرخصة برخصة جنو العمومية والتي تستخدم برنامج Bison توزيع الملفات التي تُمثل مُدخلات Bison. وبالطبع، يُمكنها أيضًا تضمين الملفات المُولّدة.

يستخدم

نظرًا لأن Bison كُتب كبديل لـ Yacc، وهو متوافق معه إلى حد كبير، يمكن إدخال الشيفرة البرمجية من العديد من المشاريع التي تستخدم Bison إلى Yacc بنفس السهولة. وهذا ما يجعل من الصعب تحديد ما إذا كان المشروع "يستخدم" شيفرة مصدرية خاصة بـ Bison أم لا. في كثير من الحالات، يمكن استبدال "استخدام" Bison بسهولة باستخدام Yacc أو أحد مشتقاته الأخرى.

يحتوي Bison على ميزات غير موجودة في Yacc، لذلك يمكن القول حقًا أن بعض المشاريع "تستخدم" Bison، لأن Yacc لن يكون كافيًا.

القائمة التالية هي للمشاريع المعروفة بأنها "تستخدم" Bison بالمعنى الأوسع، أي أنها تستخدم أدوات تطوير البرمجيات الحرة وتوزع التعليمات البرمجية التي تهدف إلى إدخالها في Bison أو حزمة متوافقة مع Bison.

مثال كامل لمحلل إعادة الدخول

يوضح المثال التالي كيفية استخدام Bison و flex لكتابة برنامج آلة حاسبة بسيط (يقتصر على الجمع والضرب) وبرنامج لإنشاء شجرة بناء جملة مجردة . يوفر الملفان التاليان تعريف وتنفيذ وظائف شجرة بناء الجملة.

/* * Expression.h * تعريف البنية المستخدمة لبناء شجرة بناء الجملة. */ #ifndef __EXPRESSION_H__ #define __EXPRESSION_H__/** * @brief نوع العملية */ typedef enum tagEOperationType { eVALUE , eMULTIPLY , eADD } EOperationType ;/** * @brief بنية التعبير */ typedef struct tagSExpression { EOperationType type ; /* /< نوع العملية */int value ; /* /< صالح فقط عندما يكون النوع eVALUE */ struct tagSExpression * left ; /* /< الجانب الأيسر من الشجرة */ struct tagSExpression * right ; /* /< الجانب الأيمن من الشجرة */ } SExpression ;/** * @brief يُنشئ مُعرّفًا * @param value القيمة العددية * @return التعبير أو NULL في حالة عدم وجود ذاكرة */ SExpression * createNumber ( int value );/** * @brief تُنشئ عملية * @param type نوع العملية * @param left المعامل الأيسر * @param right المعامل الأيمن * @return التعبير أو NULL في حالة عدم وجود ذاكرة */ SExpression * createOperation ( EOperationType type , SExpression * left , SExpression * right );/** * @brief حذف تعبير * @param b التعبير */ void deleteExpression ( SExpression * b );#endif /* __EXPRESSION_H__ */
/* * Expression.c * تنفيذ الدوال المستخدمة لبناء شجرة بناء الجملة. */#include "Expression.h"#include <stdlib.h>/** * @brief تخصيص مساحة للتعبير * @return التعبير أو NULL إذا لم تكن الذاكرة كافية */ static SExpression * allocateExpression () { SExpression * b = ( SExpression * ) malloc ( sizeof ( SExpression ));إذا كان ( b == NULL ) فأرجع NULL ؛b -> type = eVALUE ; b -> value = 0 ;b -> left = NULL ; b -> right = NULL ;أعد b ؛ }SExpression * createNumber ( int value ) { SExpression * b = allocateExpression ();إذا كان ( b == NULL ) فأرجع NULL ؛b -> type = eVALUE ; b -> value = value ;أعد b ؛ }SExpression * createOperation ( EOperationType type , SExpression * left , SExpression * right ) { SExpression * b = allocateExpression ();إذا كان ( b == NULL ) فأرجع NULL ؛b -> type = type ; b -> left = left ; b -> right = right ;أعد b ؛ }void deleteExpression ( SExpression * b ) { if ( b == NULL ) return ;حذف التعبير ( ب -> يسار )؛ حذف التعبير ( ب -> يمين )؛حر ( ب )؛ }

سيتم إنشاء الرموز المميزة التي يحتاجها محلل Bison باستخدام flex.

% {/* * ملف Lexer.l * لتشغيل محلل المفردات، قم بتشغيل الأمر التالي: "flex Lexer.l" */#include "Expression.h" #include "Parser.h"#include <stdio.h>% }% خيار outfile = "Lexer.c" ملف الرأس = " Lexer.h" % خيار warn nodefault% خيار إعادة الدخول noyywrap أبداً - تفاعلي nounistd % خيار bison - جسر%%[ \ r \ n \ t ] * { continue ; /* تخطي الفراغات. */ } [ 0-9 ] + { sscanf ( yytext , "%d" , & yylval -> value ); return TOKEN_NUMBER ; }"*" { return TOKEN_STAR ; } "+" { return TOKEN_PLUS ; } "(" { return TOKEN_LPAREN ; } ")" { return TOKEN_RPAREN ; }. { continue ; /* تجاهل الأحرف غير المتوقعة. */ }%%int yyerror ( SExpression ** expression , yyscan_t scanner , const char * msg ) { fprintf ( stderr , "خطأ: %s \n " , msg ); return 0 ; }

عادةً ما تكون أسماء الرموز محايدة: "TOKEN_PLUS" و"TOKEN_STAR"، وليس "TOKEN_ADD" و"TOKEN_MULTIPLY". على سبيل المثال، إذا كنا ندعم عملية الجمع الأحادية "+" (كما في "+1")، فسيكون من الخطأ تسمية هذه العملية "+" بـ "TOKEN_ADD". في لغة مثل C، يشير "int *ptr" إلى تعريف مؤشر، وليس إلى عملية ضرب: سيكون من الخطأ تسمية هذه العملية "*" بـ "TOKEN_MULTIPLY".

بما أن الرموز يتم توفيرها بواسطة flex، فيجب علينا توفير وسائل الاتصال بين المحلل اللغوي والمحلل المعجمي . [ 23 ] يتم تحديد نوع البيانات المستخدم للاتصال، YYSTYPE ، باستخدام تعريف Bison %union .

بما أننا نستخدم في هذا المثال النسخة القابلة لإعادة الدخول من كلٍّ من flex و yacc، فإننا مضطرون لتوفير معلمات لدالة yylex عند استدعائها من yyparse . [ 23 ] ويتم ذلك من خلال تعريفات Bison %lex-param و %parse-param . [ 24 ]

% {/* * ملف Parser.y * لتشغيل برنامج التحليل، قم بتشغيل الأمر التالي: "bison Parser.y" */#include "Expression.h" #include "Parser.h" #include "Lexer.h"// الإشارة إلى التنفيذ المقدم في Lexer.l int yyerror ( SExpression ** expression , yyscan_t scanner , const char * msg );% }% code requires { typedef void * yyscan_t ; }% إخراج "Parser.c" % تعريف "Parser.h"% define api . pure % lex - param { yyscan_t scanner } % parse - param { SExpression ** expression } % parse - param { yyscan_t scanner }% union { int value ; SExpression * expression ; }% token TOKEN_LPAREN "(" % token TOKEN_RPAREN ")" % token TOKEN_PLUS "+" % token TOKEN_STAR "*" % token < value > TOKEN_NUMBER "number"% نوع < تعبير > تعبير/* الأسبقية (تصاعدية) والترابطية:  a+b+c هي (a+b)+c: ترابطية يسارية.  a+b*c هي a+(b*c): أسبقية "*" أعلى من أسبقية "+". */ % left "+" % left "*"%%المدخلات : تعبير { * التعبير = $1 ; } ;expr : expr [ L ] "+" expr [ R ] { $$ = createOperation ( eADD , $L , $R ); } | expr [ L ] "*" expr [ R ] { $$ = createOperation ( eMULTIPLY , $L , $R ); } | "(" expr [ E ] ")" { $$ = $E ; } | "number" { $$ = createNumber ( $1 ); } ;%%

الكود اللازم للحصول على شجرة بناء الجملة باستخدام المحلل اللغوي الذي تم إنشاؤه بواسطة Bison والماسح الضوئي الذي تم إنشاؤه بواسطة flex هو التالي.

/* * ملف main.c */#include "Expression.h" #include "Parser.h" #include "Lexer.h"#include <stdio.h>int yyparse ( SExpression ** expression , yyscan_t scanner );SExpression * getAST ( const char * expr ) { SExpression * expression ; yyscan_t scanner ; YY_BUFFER_STATE state ;إذا ( yylex_init ( & scanner )) { /* تعذر التهيئة */ أرجع NULL ; }state = yy_scan_string ( expr , scanner );إذا ( yyparse ( & expression , scanner )) { /* خطأ في التحليل */ إرجاع NULL ; }yy_delete_buffer ( state , scanner );yylex_destroy ( scanner );return expression ; }int evaluate ( SExpression * e ) { switch ( e -> type ) { case eVALUE : return e -> value ; case eMULTIPLY : return evaluate ( e -> left ) * evaluate ( e -> right ); case eADD : return evaluate ( e -> left ) + evaluate ( e -> right ); default : /* يجب ألا يكون هنا */ return 0 ; } }int main ( void ) { char test [] = " 4 + 2*10 + 3*( 5 + 1 )" ; SExpression * e = getAST ( test ); int result = evaluate ( e ); printf ( "نتيجة '%s' هي %d \n " , test , result ); deleteExpression ( e ); return 0 ; }

فيما يلي ملف makefile بسيط لبناء المشروع.

ملفالملفات = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -ansiاختبار : $( FILES ) $( CC ) $( CFLAGS ) $( FILES ) -o اختبارLexer.c : Lexer . l flex Lexer.lParser.c : محلل . ي ليكسر . ج البيسون Parser.yتنظيف : rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test

انظر أيضاً

  • برنامج Berkeley Yacc (byacc) – بديل آخر مجاني لبرنامج Yacc، ويشترك في نفس مؤلف برنامج GNU Bison. 
  • ANTLR أداة أخرى للتعرف على اللغة، ومولد محلل نحوي آخر مفتوح المصدر

مراجع

  1. 1 2 كوربيت، روبرت بول (يونيو 1985). الدلالات الثابتة واستعادة أخطاء المترجم (دكتوراه). جامعة كاليفورنيا، بيركلي . DTIC ADA611756 .
  2. ↑ أكيم ديماي (25 سبتمبر 2021). "Bison 3.8.2" .
  3. ↑ "اللغة والقواعد (Bison 3.8.1)" . www.gnu.org . تاريخ الاسترجاع: 26-12-2021 .
  4. ↑ دليل بيسون: مقدمة.
  5. ↑ ليفين، جون (أغسطس 2009). فليكس وبيسون . دار نشر أورايلي. رقم ISBN 978-0-596-15597-1.
  6. ↑ "المؤلفون" . bison.git. GNU Savannah . تم الاسترجاع في 26-08-2017 .
  7. ↑ دليل بيسون: محلل نحوي نقي (قابل لإعادة الدخول)
  8. ↑ دليل البيسون: ملخص إعلان البيسون
  9. ↑ دليل استخدام بايسون: شروط استخدام بايسون
  10. ↑ ملف شفرة مصدرية، parse-gram.c، يتضمن الاستثناء
  11. ↑ "parse-gram.y" . bison.git. GNU Savannah . تم الاسترجاع في 29-07-2020 .
  12. ↑ "LexerParser in CMake" . github.com .
  13. ↑ تغييرات وميزات جديدة وإصلاحات في سلسلة إصدارات GCC 3.4
  14. ↑ تغييرات وميزات جديدة وإصلاحات في سلسلة إصدارات GCC 4.1
  15. ↑ تعريف قواعد لغة غولانغ
  16. ^ "Parser.yy - مستودع GNU LilyPond Git" . git.savannah.gnu.org .
  17. ↑ "4. تحليل SQL - flex & bison [ كتاب ] " .
  18. ↑ "ملف المصدر لبرنامج GNU Octave: Libinterp/Parse-tree/Oct-parse.cc" . مؤرشف من الأصل بتاريخ 13 سبتمبر 2019. تم الاطلاع عليه بتاريخ 11 مارس 2016 .
  19. ↑ "ما الجديد في بيرل 5.10.0؟" . perl.org.
  20. ↑ "مرحلة التحليل" . postgresql.org. 30 سبتمبر 2021.
  21. ↑ "Ruby MRI Parser" . github.com .
  22. ^ "محلل XML الخاص بـ syslog-ng" . جيثب.كوم . 14 أكتوبر 2021.
  23. دليل Flex 1 2 : الماسحات الضوئية C مع محللات Bison (مؤرشف بتاريخ 17-12-2010 على Wayback Machine)
  24. ↑ دليل Bison: اصطلاحات الاستدعاء للمحللات البحتة

للمزيد من القراءة