Answer Happy

Construct a Syntax-Directed Translation scheme that takes strings of a's, b's and c's as input and produces as output the number of substrings in the input string that correspond to the pattern a(a|b)* c+(a∣b)∗b. For example, the translation of the input string "abbcabcababc" is "3" as shown in the following figure: Your solution should include: a) A context-free grammar that generates all strings of a's, b's and c's. b) Semantic attributes for the grammar symbols order on the tree. c) For each production of the grammar a set of rules for evaluation of the semantic attributes. d) A justification that your solution is correct.