تصميم_مترجمات_شرائح_الوحدة_الثانية_مترجمة_حائل (1).pdf

Compiler Design CSCE 354 Dr.Razauddin University of Hail, Kingdom of Saudi Arabia 2024-2025  Chapter 2 Lexical Analysis: Application of regular expressions in lexical scanners  OVERVIEW To translat...

Compiler Design CSCE 354 Dr.Razauddin University of Hail, Kingdom of Saudi Arabia 2024-2025  Chapter 2 Lexical Analysis: Application of regular expressions in lexical scanners  OVERVIEW To translate a program from one language into another, a compiler must first pull it apart and understand its structure and meaning, then put it together in a different way. ً.‫ مث تجميعه بطريقة مختلفة‬،‫ يجب عىل املرتجم أوال تفكيكه وفهم بنيته ومعناه‬،‫ لرتجمة برنامج من لغة إىل أخرى‬ The front end of the compiler performs analysis; the back end does synthesis. The analysis ً is usually broken up into ‫ وعادة ما يمت تقسمي التحليل إىل‬.‫ يقوم الطرف األمامي للمرتجم بإجراء التحليل؛ ويقوم الطرف الخلفي بالتوليف‬ Lexical analysis breaking the input into individual words or "tokens"; Syntax analysis parsing the phrase structure of the program; Semantic analysis calculating the program's meaning. What is a Token? ‫ ما هو الرمز؟‬ A lexical token is a sequence of characters that can be treated as a unit in the grammar of the programming languages. ‫ الرمز املعجمي هو سلسلة من األحرف اليت ميكن التعامل معها كوحدة يف قواعد لغات‬ Example of tokens:.‫الربمجة‬ Type token (id, number, real,... ) Punctuation tokens (IF, void, return,... ) :‫ مثال عىل الرموز‬... ) ،real ،number ،id( ‫ رمز النوع‬ Alphabetic tokens (keywords)... ) ،return ،void ،IF( ‫ رموز عالمات الرتقمي‬ )‫ الرموز األبجدية (الكلمات األساسية‬ Lexical Analysis is the first phase of the ً compiler also known as a scanner..‫ التحليل املعجمي هو املرحلة األوىل من املرتجم واملعروف أيضا بامس املاسح الضويئ‬ It converts the High level input program into a sequence of Tokens..‫ يحول برنامج اإلدخال عايل املستوى إىل سلسلة من الرموز‬ 1.Lexical Analysis can be implemented with the Deterministic finite Automata..‫ ميكن تنفيذ التحليل املعجمي باستخدام األمتتة املحدودة الحمتية‬ 2.The output is a sequence of tokens that is sent to the parser for syntax analysis..‫يكون الناتج عبارة عن سلسلة من الرموز اليت يمت إرسالها إىل املحلل لتحليل بناء الجملة‬  LEXICAL TOKENS ▪ A lexical token is a sequence of characters that can be treated as a unit in the grammar of a programming language. ‫ الرمز املعجمي هو عبارة عن سلسلة من األحرف اليت ميكن التعامل‬.‫معها كوحدة يف قواعد لغة الربمجة‬ ▪ A programming language classifies lexical tokens into a finite set of token types. ‫ تصنف لغة الربمجة الرموز املعجمية إىل مجموعة محدودة من أنواع‬ ▪ For example, some of the token types of a typical programming language are.‫الرموز‬ ‫ بعض أنواع الرموز يف لغة الربمجة المنوذجية هي‬،‫ عىل سبيل املثال‬ Type Examples Type Examples ID foo n14 last COMMA , NUM 73 0 00 515 082 NOTEQ != REAL 66.1.5 10. 1e67 5.5e-10 LPAREN ( IF if RPAREN ) Punctuation tokens such as IF, VOID, RETURN constructed from alphabetic characters are called reserved words and, in most languages, cannot be used as identifiers. ُ ُ ‫ وال‬،‫املنشأة من أحرف أبجدية بالكلمات املحجوزة‬RETURN ‫و‬VOID ‫و‬IF ‫ تمسى عالمات الرتقمي مثل‬.‫ميكن استخدامها كمعرفات يف معظم اللغات‬ Examples of nontokens comment preprocessor directive #include preprocessor directive #define NUMS 5, 6 macro NUMS  REGULAR EXPRESSIONS.‫ كل تعبري عادي ميثل مجموعة من السالسل‬ Each regular expression stands for a set of strings. Symbol: For each symbol a in the alphabet of the language, the regular expression a denotes the :‫ الرمز‬ language containing just the string a. ‫إىل اللغة اليت تحتوي‬a ‫ يشري التعبري العادي‬،‫يف أبجدية اللغة‬a ‫ بالنسبة لكل رمز‬.‫فقط‬a ‫عىل السلسلة‬ Alternation: Given two regular expressions M and N, the alternation operator written as a vertical bar makes a new regular expression M N. A string is in the language of M N if it is in the language of M or in the language of N. Thus, the language of a b contains the two strings a and b. :‫ التناوب‬ ً ‫تعبريا ع‬ ‫اديا‬ ً ‫ فإن عامل التناوب املكتوب كخط عمودي ينئش‬،N‫و‬M ‫ بالنظر إىل تعبريين عاديني‬ ً a ‫ تحتوي لغة‬،‫وبالتايل‬N. ‫أو يف لغة‬M ‫إذا كانت يف لغة‬M N ‫تكون السلسلة يف لغة‬M N. ‫جديدا‬ b.‫و‬a ‫عىل السلسلتني‬b Concatenation: Given two regular expressions M and N, the concatenation operator · makes a new regular expression M · N. A string is in the language of M · N if it is the concatenation of any two strings and such that is in the language of M and is in the language of N. Thus, the regular expression (a b) · a defines the language :‫ التجميع‬ containing the two strings aa and ba. ‫ يقوم عامل التجميع · بإنشاء تعبري عادي‬،N‫و‬M ‫ يف حالة وجود تعبريين عاديني‬ ‫ويف لغة‬M ‫ بحيث تكون يف لغة‬،‫إذا كانت عبارة عن تجميع ألي سلسلتني‬M · N ‫تكون السلسلة يف لغة‬M · N. ‫جديد‬ ba.‫و‬aa ‫يحدد اللغة اليت تحتوي عىل السلسلتني‬a · b( · a ( ‫ فإن التعبري العادي‬،‫وبالتايل‬N. Epsilon: The regular expression represents a language whose only string is the empty string. Thus, (a · b) represents the language {"", "ab"}. ab"}." ,""{ ‫اللغة‬a · b( ( ‫ ميثل‬،‫ وبالتايل‬.‫ميثل التعبري العادي لغة تكون سلسلتها الفارغة هي السلسلة الوحيدة‬Epsilon: Repetition: Given a regular expression M, its Kleene closure is M*. A string is in M* if it is the concatenation of zero or more strings, all of which are in M. Thus, ((a b) · a)* represents the infinite set {"", "aa", "ba", "aaaa", "baaa", "aaba", "baba", "aaaaaa", }. M* ‫تكون السلسلة يف‬M*. ‫ يكون إغالق كليني الخاص به هو‬،M ‫ يف حالة وجود تعبري عادي‬:‫ التكرار‬ ,""{ ‫املجموعة الالنهائية‬a b) · a(* (( ‫ ميثل‬،‫وبالتايل‬M. ‫ وكلها يف‬،‫إذا كانت عبارة عن تجميع لسالسل صفرية أو أكرث‬ aa", "ba", "aaaa", "baaa", "aaba", "baba", "aaaaaa", }." Using symbols, alternation, concatenation, epsilon, and Kleene closure we can specify the set of ASCII characters corresponding to the lexical tokens of a programming language. ‫ ميكننا‬،‫ باستخدام الرموز والتناوب والتسلسل واإلبسيلون وإغالق كليني‬.‫املقابلة للرموز املعجمية للغة الربمجة‬ASCII ‫تحديد مجموعة أحرف‬ Examples (0 | 1)* · 0 Binary numbers that are multiples of two. b*(abb*)*(a| ) Strings of a's and b's with no consecutive a's. (a|b)*aa(a|b)* Strings of a's and b's containing consecutive a's.  EXAMPLES ab | c (a · b) | c [abcd] (a | b | c | d) [b-g] [bcdefg] [b-gM-Qkr] [ bcdefgMNOPQkr] The empty string. Another way to write the empty string. M|N Alternation, choosing from M or N. M·N Concatenation, an M followed by an N. MN Another way to write concatenation. M* Repetition (zero or more times). M+ Repetition, one or more times. M? Optional, zero or one occurrence of M. [a zA Z] Character set alternation.. A period stands for any single character except newline. "a.+*" Quotation, a string in quotes stands for itself literally. Regular expressions have the capability to express finite languages by defining a pattern for finite strings of symbols. ‫ تمتتع التعبريات العادية بالقدرة عىل التعبري عن‬.‫لغات محدودة من خالل تحديد منط لسالسل محدودة من الرموز‬ The grammar defined by regular expressions is known as regular grammar. The language defined by regular grammar is known as regular language. ُ.‫ تعرف القواعد النحوية اليت تحددها التعبريات العادية بامس القواعد النحوية العادية‬ ُ.‫تعرف اللغة اليت تحددها القواعد النحوية العادية بامس اللغة العادية‬ Operations ‫العمليات‬ :‫ العمليات املختلفة عىل اللغات هي‬ The various operations on languages are: ‫عىل النحو التايل‬M ‫و‬L ‫ ُيكتب اتحاد لغتني‬ ❑ Union of two languages L and M is written as M} ‫يف‬s ‫أو‬L ‫يف‬L U M = {s | s L U M = {s | s is in L or s is in M} ‫عىل النحو التايل‬M ‫و‬L ‫ُيكتب ربط لغتني‬ ❑ Concatenation of two languages L and M is written as M} ‫يف‬t ‫و‬L ‫يف‬LM = {st | s LM = {st | s is in L and t is in M} ‫عىل النحو التايل‬L ‫ُيكتب إغالق كليني للغة‬ ❑ The Kleene Closure of a language L is written as L. ‫صفر أو أكرث من حاالت حدوث اللغة‬L* = L* = Zero or more occurrence of language L. Notations ‫ تدوينات‬ If r and s are regular expressions denoting the languages L(r) and L(s), then ‫ فإن‬،L(s)‫و‬L(r) ‫تعبريات منتظمة تشري إىل اللغتني‬s ‫و‬r ‫ إذا كانت‬ ▪ Union : (r)|(s) is a regular expression denoting L(r) U L(s) L(r) U L(s) ‫تعبري منتظم يشري إىل‬r)|(s) ( :‫ االتحاد‬ ▪ Concatenation : (r)(s) is a regular expression denoting L(r)L(s) L(r)L(s) ‫تعبري منتظم يشري إىل‬r)(s) ( :‫ التسلسل‬ ▪ Kleene closure : (r)* is a regular expression denoting (L(r))* L(r))*( ‫تعبري منتظم يشري إىل‬r)* ( :‫ إغالق كلني‬ ▪ (r) is a regular expression denoting L(r) L(r) ‫(تعبري منتظم يشري إىل‬r) Precedence and Associativity ‫ األسبقية والرتابطية‬ ▪ *, concatenation (.), and | (pipe sign) are left associative ‫ و| (عالمة األنبوب) هي ترابطية يسارية‬،).( ‫ والتسلسل‬، ‫ * لها أعىل أولوية‬ ▪ * has the highest precedence ▪ Concatenation (.) has the second highest precedence..‫) لها ثاين أعىل أولوية‬.( ‫ التسلسل‬ ▪ | (pipe sign) has the lowest precedence of all..‫ | (عالمة األنبوب) لها أدىن أولوية عىل اإلطالق‬ Representation occurrence of symbols using regular expressions letter = [a – z] or [A – Z] digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 or [0-9] sign = [ + | - ] Representation of language tokens using regular expressions Decimal = (sign)?(digit)+ Identifier = (letter)(letter | digit)* Regular expressions for some tokens. ▪ Comments or white space does not report back to the parser..‫ ال يمت إرسال التعليقات أو املسافات البيضاء إىل املحلل‬ ▪ Instead, the white space is discarded and the lexer resumed. ً.‫ يمت تجاهل املسافات البيضاء واستئناف املحلل املعجمي‬،‫بدال من ذلك‬ ▪ The comments for this lexer begin with two dashes, contain only alphabetic characters, and end with newline. ‫ وتنتهي بسطر‬،‫ وتحتوي فقط عىل أحرف أبجدية‬،‫تبدأ التعليقات لهذا املحلل املعجمي برشطتني‬.‫جديد‬ ▪ Finally, a lexical specification should be complete, always matching some initial substring of the input; we can always achieve this by having a rule that matches any single character (and in this ً ،‫ يجب أن تكون املواصفات املعجمية كاملة‬،‫أخريا‬ case, prints an "illegal character" error message and continues). ً ً ‫وتطابق دامئا بعض السالسل الفرعية األولية للمدخالت؛ ميكننا دامئا تحقيق ذلك من خالل وجود‬ ▪ These rules are a bit ambiguous..)‫ تطبع رسالة خطأ "حرف غري قانوين" وتسمتر‬،‫قاعدة تطابق أي حرف واحد (ويف هذه الحالة‬ ▪ For example, does if8 match as a single identifier or as the two tokens if and 8?.‫هذه القواعد غامضة بعض اليشء‬ ‫؟‬8‫و‬if ‫كمعرف واحد أم كرمزين‬if8 ‫ هل يتطابق‬،‫عىل سبيل املثال‬ ▪ There are two important disambiguation rules used by Lex, JavaCC, SableCC, and other similar lexical-analyzer generators: ‫ومولدات املحلل‬SableCC ‫و‬JavaCC ‫و‬Lex ‫هناك قاعدتان مهمتان لتوضيح الغموض يستخدمهما‬ :‫املعجمي املماثلة األخرى‬ Regular expressions for some tokens. ▪ There are two important disambiguation rules used by Lex, JavaCC, SableCC, and other similar lexical-analyzer generators: JavaCC ‫و‬Lex ‫هناك قاعدتان مهمتان لتوضيح الغموض تستخدمهما‬ :‫ومولدات املحلل املعجمي األخرى املشابهة‬SableCC ‫و‬ ▪ Longest match: The longest initial substring of the input that can match any regular expression is taken as the next token. ‫ يمت أخذ أطول سلسلة فرعية أولية من املدخالت اليت ميكنها‬:‫أطول تطابق‬.‫مطابقة أي تعبري عادي كرمز ممزي‬ ▪ Rule priority: For a particular longest initial substring, the first regular expression that can match determines its token-type. This means that the order of writing down the regular-expression rules has significance. ‫ يحدد أول تعبري‬،‫ بالنسبة لسلسلة فرعية أولية أطول معينة‬:‫أولوية القاعدة‬ ‫ وهذا يعين أن ترتيب كتابة‬.‫عادي ميكن مطابقته نوع الرمز املمزي الخاص بها‬ ▪ For example, does if8 match as a single identifier or as the two tokens if and 8?.‫قواعد التعبري العادي له أهمية‬ ‫؟‬8‫و‬if ‫كمعرف واحد أم كرمزين ممزيين‬if8 ‫ هل تتطابق‬،‫عىل سبيل املثال‬ ▪ Thus, if8 matches as an identifier by the longest-match rule, and if matches as a reserved word by rule-priority. ً ‫ككلمة‬if ‫ وتتطابق‬،‫كمعرف وفقا لقاعدة أطول تطابق‬if8 ‫ تتطابق‬،‫وبالتايل‬ ً.‫محجوزة وفقا ألولوية القاعدة‬ Exercise The input source code is converted into a sequence of tokens..‫يمت تحويل كود املصدر املدخل إىل سلسلة من الرموز‬ sum = a + b; sum = a + b; Steps in Lexical Analysis: :‫خطوات التحليل املعجمي‬ Input Source Code: :‫ كود املصدر املدخل‬ The lexical analyzer (lexer) reads the source.‫األحرف‬ code‫من‬as‫كسلسلة‬a sequence of ‫يقرأ املحلل املعجمي كود املصدر‬ characters. Tokenization: :‫التجزئة‬ The lexer divides this sequence into a list of meaningful symbols, known as tokens. Each token represents a basic element of the programming language. ‫ واملعروفة‬،‫يقمس املحلل املعجمي هذا التسلسل إىل قامئة من الرموز ذات املعىن‬ ً.‫أساسيا من عنارص لغة الربمجة‬ ً ‫عنرصا‬ ‫ ميثل كل رمز‬.‫بالرموز‬  Int – keyword Sum – Identifier = - Assigned operator int sum = a + b; a - identifier + - Addition operator b – identifier ; - Semicolon (Delimiter) Output Tokens: For the given source code, the lexer might produce the following tokens: :‫ رموز اإلخراج‬ :‫ قد ينتج املحلل املعجمي الرموز التالية‬،‫ بالنسبة لرمز املصدر املعطى‬ Key Points: :‫ النقاط الرئيسية‬ Whitespace and Comments: The lexer typically ignores whitespace and comments, as they do not affect the meaning of the code. ً.‫ ألنها ال تثثر عىل معىن الكود‬،‫ يتجاهل املحلل املعجمي عادة املسافات البيضاء والتعليقات‬:‫ املسافات البيضاء والتعليقات‬ Error Handling: If the lexer encounters an invalid sequence of characters that cannot be classified into a valid token, it raises an error. For example, if the input contains an unexpected character like #, which is not valid in the given context, an error ً is reported..‫ فإنه يثري خطأ‬،‫ إذا واجه املحلل املعجمي تسلسال غري صالح من األحرف اليت ال ميكن تصنيفها إىل رمز صالح‬:‫ معالجة األخطاء‬.‫ فسيمت اإلبال عن خطأ‬،‫ وهو غري صالح يف السياق املعطى‬،# ‫ إذا احتوى اإلدخال عىل حرف غري متوقع مثل‬،‫عىل سبيل املثال‬  int sum = a + b; Output: KEYWORD: int ID: sum ASSIGN: = ID: a PLUS: + ID: b SEMICOLON: ; Exercise The input source code is converted into a sequence of tokens. def greet(name): print("Hello, " + name + "!") greet("Alice") Steps in Lexical Analysis: Input Source Code: The lexical analyzer (lexer) reads the source code as a sequence of characters. Tokenization: The lexer divides this sequence into a list of meaningful symbols, known as tokens. Each token represents a basic element of the programming language.  def, print – keyword def greet(name): greet, name – Identifier print("Hello, " + name + "!") + - operator greet("Alice") (), “ - Punctuation “Hello” - Literal b – identifier - White Space (Delimiter) Output Tokens: For the given source code, the lexer might produce the following tokens: Key Points: Whitespace and Comments: The lexer typically ignores whitespace and comments, as they do not affect the meaning of the code. Error Handling: If the lexer encounters an invalid sequence of characters that cannot be classified into a valid token, it raises an error. For example, if the input contains an unexpected character like #, which is not valid in the given context, an error is reported. By Students: Convert input source code into sequence of token? 1. total = 3.14 * radius * radius; 2. if (x >= 10) { y = x * 2; } 3. x = 5 + 3; 4. a = b - 2; Lexical Analysis (Tokens): 1. total - Identifier 2. = - Operator (Assignment) 3. 3.14 - Literal (Floating-point number) 4. * - Operator (Multiplication) 20. * - Operator (Multiplication) 5. radius - Identifier 21. 2 - Literal (Integer) 6. * - Operator (Multiplication) 22. ; - Delimiter (Semicolon) 7. radius - Identifier 23. } - Punctuation (Right Brace) 8. ; - Delimiter (Semicolon) 24. x - Identifier 9. if - Keyword 25. = - Operator (Assignment) 10. ( - Punctuation (Left Parenthesis) 26. 5 - Literal (Integer) 11. x - Identifier 27. + - Operator (Addition) 12. >= - Operator (Greater than or Equal to) 28. 3 - Literal (Integer) 13. 10 - Literal (Integer) 29. ; - Delimiter (Semicolon) 14. ) - Punctuation (Right Parenthesis) 30. a - Identifier 15. { - Punctuation (Left Brace) 31. = - Operator (Assignment) 16. y – Identifier 32. b - Identifier 17. = - Operator (Assignment) 33. - - Operator (Subtraction) 18. x - Identifier 34. 2 - Literal (Integer) 35. ; - Delimiter (Semicolon) Lexem Token total, radius, x, y ,a , b Identifier = , * , >= , - Operator 3.14 Literal (Floating-point number) ; Delimiter SEMICOLON if Keyword ( ) , {} Punctuation 10 , 2 , 5 , 3 , 2 Literal (Integer)