أسئلة المقال وتتبع الشيفرة وتصحيح الأخطاء وكتابة الشيفرة في بنك أسئلة الأسبوع:
هياكل البيانات والخوارزميات (DSA27) · الأسبوع 15
The Principles of Language Translation (Lecture 15)
هذه اختبارات للتدريب الذاتي، تُحفظ إجاباتك على هذا الجهاز فقط ولا تُرسل إلى أحد. الأسئلة والشرح بالإنجليزية لغة المقرر.
-
The job of the lexer is to:
Values are the evaluator's job (a), balanced parentheses and the tree the parser's (c, d). The lexer knows nothing about structure.
-
tokenize("12+3")returns a list of how many tokens?['12', '+', '3'].12is one token: the lexer keeps reading while the next character is a digit. -
calculate("3 + * 4")fails. Which stage rejects it?Every token is valid, so the lexer accepts it (b); but after the
+,factorfinds*, which cannot start a factor:ValueError: unexpected '*'. Nothing reaches the evaluator (c). -
"AST" stands for:
"Abstract" because it drops the grammar's bookkeeping — the parentheses, and the calls that only passed a value up.
-
In the grammar,
*binds more tightly than+because:An
expris a sequence ofterms, and every*is consumed inside atermbeforeexprsees the next+; so*ends up deeper in the tree. There is no table (a) — that was shunting-yard. -
calculate("2 + 3 * 4 - 1")returns:2 + (3 * 4) - 1 = 13. 19 (a) ignores precedence:((2 + 3) * 4) - 1. -
The root of the AST of
2 * 3 + 4is:(2 * 3) + 4: the last operator applied is the root. -
The root of the AST of
(1 + 2) * (3 - 4)is:Each parenthesised group is a factor of the one
term(…) * (…). Parentheses (c) never appear in the tree. -
1 - 2 - 3evaluates to -4 because subtraction is:Left-associative: the leftmost operation first.
1 - (2 - 3)(c) would be 2. -
A student writes
exprright-recursively: parse aterm; if the next token is+or-, returnBinOp(op, term, self.expr()). What does it give for8 - 4 - 2?It builds
8 - (4 - 2) = 6: the recursive call parses the whole rest of the line and hangs it on the right. The correct value is 2 (a). -
The rule
expr := expr '+' term | termis turned directly into a method whose first line isleft = self.expr(). On the input3it:exprcallsexprat the sameposition, before reading anything, so no call is ever closer to a base case. Python stops it at its recursion limit, so it does use memory — a frame per call (d is wrong). -
In recursive descent, the EBNF repetition
( … )*becomes:A
whileloop that runs whilepeek()is one of the operators. A rule name becomes a call (a);|becomes anif(c). -
Parsing
1 + 2 * 3, how many times isfactorcalled?One per number:
1,2and3. (Measured: 3 calls.) -
The tree our parser builds for
-5 + 2is:Unary minus is a
factor, so it binds only the5:(0 - 5) + 2 = -3. Option (a) is the tree a parser builds if unary minus callsexprinstead offactor(W15-B3). The lexer never produces negative numbers (c):-5is two tokens. -
evaluatevisits the nodes of the tree in:An operator can be applied only once both operand values are known: children first.
-
The post-order sequence of the AST of
(3 + 4) * 2is:Left subtree
3 4 +, right subtree2, then the root*. It is also the postfix form of Lecture 06. -
parseraisesValueErrorif tokens are left over afterexprreturns. Without that check:exprparses3 + 4and stops at the), which no rule can use; only the final check notices it. (a) and (c) fail insidefactoranyway. -
Each pair of parentheses costs the parser about three Python frames. With Python's default limit of 1,000 frames, roughly how deeply can
calculatenest parentheses?1,000 / 3 is about 333, less a few frames already in use: measured from a script, 329 pairs work and 330 raise
RecursionError. -
The time of
calculateon an expression of n tokens is:Each stage touches each token or node a constant number of times.
-
calculate("1 + 1 + … + 1")with n numbers: how deep does the recursion ofevaluatego?The parser uses a loop (a is about the parser), but it builds a tree of height n - 1, and
evaluaterecurses once per level. log2 n (b) is the balanced case. -
When you run a
.pyfile, CPython:The bytecode is in
__pycache__;disshows it. -
Compared with the Week 6 route (shunting-yard, then
evaluate_postfix), the main advantage of building a tree is that:Both routes are O(n) (a). The tree route needs recursion (c), and memory for the tree (d).
18 درجات
أسئلة المقال
5 أسئلة مقالية (18 درجة). اكتب إجابتك أولًا، ثم اعرض الإجابة النموذجية ونقاط التصحيح، وقدّر درجتك بأمانة: كل نقطة تساوي درجة تقريبًا.
مجموع درجات المقال: 0 / 18
-
Name the three stages of a translator, with the input and output of each. For each, give an input that it — and only it — rejects, and the exception our calculator raises. How does a compiler differ from an interpreter?
الإجابة النموذجية ونقاط التصحيح
- Lexer: text → tokens. Rejects characters outside the language:
"3 $ 4"→ValueError(unexpected character). - Parser: tokens → tree (AST), following the grammar. Rejects valid tokens in an invalid order:
"3 + * 4","(3 + 4","3 + 4 )"→ValueError. - Evaluator: tree → value. Rejects well-formed expressions with no value:
"1 / 0"→ZeroDivisionError. - Compiler against interpreter: a compiler translates the whole program ahead of time into another program (machine code, bytecode) that runs later; an interpreter executes as it goes and produces the result. Both share the lexer and parser; a compiler replaces the evaluator by a code generator. CPython does both: compile to bytecode, then interpret it.
- Lexer: text → tokens. Rejects characters outside the language:
-
"Precedence is the shape of the grammar." Explain this sentence using the three rules of our grammar and the tree of
3 + 4 * 2. How do parentheses override precedence? Where would you add a rule for a tighter operator such as^?الإجابة النموذجية ونقاط التصحيح
expr := term (('+' | '-') term)*— an expression is a sum of terms;term := factor (('*' | '/') factor)*— a term is a product of factors.- To parse
3 + 4 * 2,exprsplits at+into the terms3and4 * 2; the*is consumed inside the second term. In the tree,*is below+:+over3and*(4, 2). Deeper nodes are evaluated first, so*"wins" — value 11. - The lower the rule an operator lives in, the tighter it binds: precedence is which rule handles the operator, not a number.
- Parentheses:
factor := '(' expr ')'makes a whole parenthesised expression a factor, the tightest level, so(3 + 4) * 2puts+below*. - A tighter operator such as
^gets a new rule betweentermandfactor, so thattermis built from it and it is built from factors (W15-C5).
-
What is associativity? Explain why
exprmust use a loop that makes the tree so far the left child. Describe what goes wrong with a right-recursiveexprand with a left-recursive one, with an input for each.الإجابة النموذجية ونقاط التصحيح
- Associativity decides how operators of the same precedence group: left-associative
1 - 2 - 3 = (1 - 2) - 3 = -4. - The loop in
exprdoesnode = BinOp(op, node, self.term()): the tree built so far becomes the left child of each new operator, so the first operation ends up deepest and is evaluated first — left associativity. - Right recursion (
expr := term ('+' expr)?) puts the recursive result — the whole rest of the line — on the right:1 - 2 - 3becomes1 - (2 - 3) = 2. No error; just a wrong answer, and only for chains of-or/(W15-B1). - Left recursion (
expr := expr '+' term) callsexprfirst, with nothing consumed: the recursion makes no progress, and every input, even3, ends inRecursionError. - The
( … )*form with a loop gives left associativity and terminates.
- Associativity decides how operators of the same precedence group: left-associative
-
Compare the two routes from infix tokens to a value: shunting-yard plus
evaluate_postfix, andParserplusevaluate. Give their costs, one advantage of each, and the connection between the postfix list and the tree.الإجابة النموذجية ونقاط التصحيح
- Stack route:
infix_to_postfix(operator stack, precedence table) thenevaluate_postfix(value stack). O(n); no recursion, so no depth limit; builds nothing but a list. - Tree route:
Parser(recursive descent) thenevaluate(post-order). O(n) too; the tree can be reused — printed, simplified, compiled — and the grammar is easy to extend (unary minus is one case infactor; the Week 6infix_to_postfixproduces5 -for-5, whichevaluate_postfixrejects). Its recursion depth follows the tree's height. - Connection: the postfix list is exactly the post-order traversal of the tree. Shunting-yard emits the post-order of a tree it never builds.
- Stack route:
-
"In a recursive-descent parser, the call stack is the parser's stack." Explain. What decides how deep it grows, and what happens when it grows too deep?
الإجابة النموذجية ونقاط التصحيح
- Each method call pushes a frame holding its own locals — including its
nodeso far and where it is in its rule. At any moment the frames on the call stack are one path of the parse tree: "inside afactor, inside aterm, inside anexpr…". Returning pops a frame and resumes the rule that called it. A hand-written parser would need its own explicit stack for this; recursion gets it for free. - Depth is set by the shape of the input, not its length: three frames per level of parentheses (
expr,term,factor); a flat chain1 + 1 + …is a loop and adds nothing to the parser's depth (but see W15-K2 forevaluate). - Too deep: Python's limit (1,000 frames by default) raises
RecursionError— at about 330 nested pairs of parentheses. Real compilers raise the limit, or use an explicit stack for deep cases.
- Each method call pushes a frame holding its own locals — including its