编译原理 第七章习题
1．给出下面表达式的逆波兰表示（后缀式）：
a*(-b+c)
a+b*(c+d/e)
not A or not(C or not D)
(A and B)or (not C or D)
后缀式分别为：
ab-c+*
abcde/+*+
A not CD not or not or
AB and C not D or or
3. 请将表达式-（a+b）*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。
三元式：
(0)（+，a, b）
(1) ( -, (0), _)
(2) (+, c, d)
(3) (*,(1),(2))
(4)（+，a, b）
(5) (+, (4), c)
(6) (-,(3),(5))
间接三元式：
(1)（+，a, b）
(2) ( -, (1), _)
(3) (+, c, d)
(4) (*,(2),(3))
(5) (+, (1), c)
(6) (-,(4),(5))
间接代码：（1）
（2）
（3）
（4）
（1）
（5）
（6）
四元式：
（0）（+，a, b, T1）
（1）（-，T1, _, T2）
（2）（+，c, d, T3）
（3）（*, T2, T3, T4）
（4）（+，a, b, T5）
（5）（+，T5, c, T6）
（6）（-，T4,T6,T7）
7.用7.5.1节的方法，把下面语句翻译成四元式序列：
While A If A=1 then C:=C+1 Else while A≤D do A:=A+2; 100 （j<, A,C,102） 101 （j , _, _, 115） 102 （j<,B,D,104） 103 （j ,_, _, 115） 104 （j=,A, 1, 106） 105 （j , _, _, 109） 106 （+, C, 1, T1） 107 （:=, T1,_, C） 108 （j , _, _, 114） 109 （j≤,A,D,111） 110 （j , _, _, 115） 111 （+, A, 2, T2） 112 （:=,T2, _, A） 113 （j ,_, _, 109） 114 （j , _, _,100） 115 第十章 3.试对以下基本块B1和B2： B1：A:=B*C D:=B/C F:=2*E G:=B*C H:=G*G F:=H*G L:=F M:=L B2：B:=3 D:=A+C E:=A*C G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L 分别应用DAG 对它们进行优化，并就以下两种情况分别写出优化后的四元式序列： （1） 假设只有G,L,M 在基本块后面还要被引用； （2） 假设只有L 在基本块后面还要被引用。 解：B1： E B C B1优化后：A:=B*C (1) G:=B*C (2) G:=B*C D:=B/C H:=G*G H:=G*G E:=A+D L:=G*H L:=G*H G:=A M:=L H:=G*G F:=H*G L:=F M:=L B2： F 3 15 A C B2优化后：B:=3 (1) G:=3*F (2) H:=A+C D:=A+C H:=A+C I:=A*C E:=A*C I:=A*C J:=H+I G:=B*F J:= H+I L:=15+J H:=D L:=15+J I:=E M:=L J:=H+I K:=15 L:=K+J M:=L 5.以下程序是某程序的最内循环，试对它进行循环优化 A:=0 I:=1 L1：B:=J+1 C:=B+I A:=C+A If I=100 GOTO L2 I:=I+1 GOTO L1 L2： 解：代码外提：B:=J+1 删除归纳变量I：由C:=B+I可知I和C成线性关系 所以I=100和C=B+100等价，即替换为：R:=100+B IF C=B GOTO L2 同理I:=I+1可替换成C:=C+1 综上所述代码优化后为： A:=0 B:=J+1 C:=B+1 R:=100+B L1：A:=C+A If C=R GOTO L2 C:=C+1 GOTO L1 L2： 第五章 5．文法S->A S|b A->SA|a (1)列出所有LR(0)项目 (2)构造LR(0)项目集规范族及识别活前缀的DFA (3)该文法是SLR的么？若是构造它的SLR分析表。 (3) Follow First S’ #a,b S #,a,b a,b A a,b a,b 中：有接受项目和移进冲突，可解决. 冲突项目I １ ＃a,b I5 , I7存在移进，归约冲突，不可解决． ∵Follow(S) ∩a∩b≠○ 所以，该文法不是SLR的 ８.证明下面的文法 S->AaAb|BbBa A->ε B->ε是LL(1)文法。 ①不含左递归； ②First(α1) ∩First(α2) ∩…=○ ③First(A) ∩Follow(A) =○ ∴该文法是LL(1)文法 Part I Writing (30 minutes) Directions：For this part, you are allowed 30 minutes to write a short essay entitled How Should Parents Help Children to Be Independent? You should write at least 150 words following the outline given below. 1. 目前不少父母为孩子包办一切 2. 为了让孩子独立, 父母应该…… How Should Parents Help Children to Be Independent? . . Part II Reading Comprehension(Skimming and Scanning) (15 minutes) Directions: In this part, you will have 15 minutes to go over the passage quickly and answer the questions on Answer Sheet 1. For questions 1-7, choose the best answer from the four choices marked [A], [B], [C] and [D]. For questions 8-10, complete the sentences with the information given in the passage. A Grassroots Remedy Most of us spend our lives seeking the natural world. To this end, we walk the dog, play golf, go fishing, sit in the garden, drink outside rather than inside the pub, have a picnic, live in the suburbs, go to the seaside, buy a weekend place in the country. The most popular leisure activity in Britain is going for a walk. And when joggers (慢跑者) jog, they don’t run the streets. Every one of them instinctively heads to the park or the river. It is my profound belief that not only do we all need nature, but we all seek nature, whether we know we are doing so or not. But despite this, our children are growing up nature-deprived (丧失). I spent my boyhood climbing trees on Streatham Common, South London. These days, children are robbed of these ancient freedoms, due to problems like crime, traffic, the loss of the open spaces and odd new perceptions about what is best for children, that is to say, things that can be bought, rather than things that can be found. The truth is to be found elsewhere. A study in the US: families had moved to better housing and the children were assessed for ADHD—attention deficit hyperactivity disorder (多动症). Those whose accommodation had more natural views showed an improvement of 19%; those who had the same improvement in material surroundings but no nice view improved just 4%. A study in Sweden indicated that kindergarten children who could play in a natural environment had less illness and greater physical ability than children used only to a normal playground. A US study suggested that when a school gave children access to a natural environment, academic levels were raised across the entire school. Another study found that children play differently in a natural environment. In playgrounds, children create a hierarchy (等级) based on physical abilities, with the tough ones taking the lead. But when a grassy area was planted with bushes, the children got much more into fantasy play, and the social hierarchy was now based on imagination and creativity. Most bullying (恃强凌弱) is found in schools where there is a tarmac (柏油碎石) playground; the least bullying is in a natural area that the children are encouraged to explore. This reminds me unpleasantly of Sunnyhill School in Streatham, with its harsh tarmac, where I used to hang about in corners fantasising about wildlife. But children are frequently discouraged from involvement with natural spaces, for health and safety reasons, for fear that they might get dirty or that they might cause damage. So, instead, the damage is done to the children themselves: not to their bodies but to their souls. One of the great problems of modern childhood is ADHD, now increasingly and expensively treated with drugs. Yet one study after another indicates that contact with nature gives huge benefits to ADHD children. However, we spend money on drugs rather than on green places. The life of old people is measurably better when they have access to nature. The increasing emphasis for the growing population of old people is in quality rather than quantity of years. And study after study finds that a garden is the single most important thing in finding that quality. In wider and more difficult areas of life, there is evidence to indicate that natural surroundings improve all kinds of things. Even problems with crime and aggressive behaviour are reduced when there is contact with the natural world. Dr William Bird, researcher from the Royal Society for the Protection of Birds, states in his study, “A natural environment can reduce violent behaviour because its restorative process helps reduce anger and impulsive behaviour.” Wild places need encouraging for this reason, no matter how small their contribution. We tend to look on nature conservation as some kind of favour that human beings are granting to the natural world. The error here is far too deep: not only do humans need nature for themselves, but the very idea that humanity and the natural world are separable things is profoundly damaging. Human beings are a species of mammals (哺乳动物). For seven million years they lived on the planet as part of nature. Our ancestral selves miss the natural world and long for contact with non-human life. Anyone who has patted a dog, stroked a cat, sat under a tree with a pint of beer, given or received a bunch of flowers or chosen to walk through the park on a nice day, understands that. We need the wild world. It is essential to our well-being, our health, our happiness. Without the wild world we are not more but less civilised. Without other living things around us we are less than human. Five ways to find harmony with the natural world Walk: Break the rhythm of permanently being under a roof. Get off a stop earlier, make a circuit of the park at lunchtime, walk the child to and from school, get a dog, feel yourself moving in moving air, look, listen, absorb. Sit: Take a moment, every now and then, to be still in an open space. In the garden, anywhere that’s not in the office, anywhere out of the house, away from the routine. Sit under a tree, look at water, feel refreshed, ever so slightly renewed. Drink: The best way to enjoy the natural world is by yourself; the second best way is in company. Take a drink outside with a good person, a good gathering: talk with the sun and the wind with birdsong for background. Learn: Expand your boundaries. Learn five species of bird, five butterflies, five trees, five bird songs. That way, you see and hear more: and your mind responds gratefully to the greater amount of wildness in your life. Travel: The places you always wanted to visit: by the seaside, in the country, in the hills. Take a weekend break, a day-trip, get out there and do it: for the scenery, for the way through the woods, for the birds, for the bees. Go somewhere special and bring specialness home. It lasts forever, after all. 注意：此部分试题请在答题卡1上作答。 1. What is the author’s profound belief? [A] People instinctively seek nature in different ways. [B] People should spend most of their lives in the wild. [C] People have quite different perceptions of nature. [D] People must make more efforts to study nature. 2. What does the author say people prefer for their children nowadays? [A] Personal freedom. [B] Things that are natural. [C] Urban surroundings. [D] Things that are purchased. 3. What does a study in Sweden show? [A] The natural environment can help children learn better. [B] More access to nature makes children less likely to fall ill. [C] A good playground helps kids develop their physical abilities. [D] Natural views can prevent children from developing ADHD. 4. Children who have chances to explore natural areas ________. [A] tend to develop a strong love for science [B] are more likely to fantasise about wildlife [C] tend to be physically tougher in adulthood [D] are less likely to be involved in bullying 5. What does the author suggest we do to help children with ADHD? [A] Find more effective drugs for them. [B] Provide more green spaces for them. [C] Place them under more personal care. [D] Engage them in more meaningful activities. 6. In what way do elderly people benefit from their contact with nature? [A] They look on life optimistically. [C] They are able to live longer. [B] They enjoy a life of better quality. [D] They become good-humoured. 7. Dr William Bird suggests in his study that ________. [A] humanity and nature are complementary to each other [B] wild places may induce impulsive behaviour in people [C] access to nature contributes to the reduction of violence [D] it takes a long time to restore nature once damaged 8. It is extremely harmful to think that humanity and the natural world can be________________________. 9. The author believes that we would not be so civilised without ________________________. 10. The five suggestions the author gives at the end of the passage are meant to encourage people to seek _________________ with the natural world. Part III Listening Comprehension (35 minutes) Section A Directions: In this section, you will hear 8 short conversations and 2 long conversations. At the end of each conversation, one or more questions will be asked about what was said. Both the conversation and the questions will be spoken only once. After each question there will be a pause. During the pause, you must read the four choices marked [A], [B], [C] and [D], and decide which is the best answer. Then mark the corresponding letter on Answer Sheet 2 with a single line through the centre. 注意：此部分试题请在答题卡2上作答。 11. [A] The man should visit the museums. [C] The beach resort is a good choice. *B+ She can’t stand the hot weather. *D+ She enjoys staying in Washington. 12. [A] Her new responsibilities in the company. [B] What her job prospects are. *C+ What the customers’ feedback is. *D+ The director’s opinion of her work. 13. [A] Combine her training with dieting. [B] Repeat the training every three days. [C] Avoid excessive physical training. [D] Include weightlifting in the program. 14. [A] When she will return home. [B] Whether she can go by herself. [C] Whether she can travel by air. [D] When she will completely recover. 15. [A] The woman knows how to deal with the police. [B] The woman had been fined many times before. [C] The woman had violated traffic regulations. [D] The woman is good at finding excuses. 16. [A] Switch off the refrigerator for a while. [B] Have someone repair the refrigerator. [C] Ask the man to fix the refrigerator. [D] Buy a refrigerator of better quality. 17. [A] He owns a piece of land in the downtown area. [B] He has got enough money to buy a house. [C] He can finally do what he has dreamed of. [D] He is moving into a bigger apartment. 18. [A] She is black and blue all over. [B] She has to go to see a doctor. [C] She stayed away from work for a few days. [D] She got hurt in an accident yesterday. Questions 19 to 21 are based on the conversation you have just heard. 19. [A] She was a bank manager. [B] She was a victim of the robbery. [C] She was a defence lawyer. [D] She was a witness to the crime. 20. [A] A tall man with dark hair and a moustache. [B] A youth with a distinguishing mark on his face. [C] A thirty-year-old guy wearing a light sweater. [D] A medium-sized young man carrying a gun. 21. [A] Identify the suspect from pictures. [C] Have her photo taken for their files. [B] Go upstairs to sign some document. [D] Verify the record of what she had said. Questions 22 to 25 are based on the conversation you have just heard. 22. [A] By reading a newspaper ad. [C] By listening to the morning news. [B] By seeing a commercial on TV. [D] By calling an employment service. 23. [A] She could improve her foreign languages. [B] She could work close to her family. [C] She could travel overseas frequently. [D] She could use her previous experiences. 24. [A] Taking management courses. [C] Working as a secretary. [B] Teaching English at a university. [D] Studying for a degree in French. 25. [A] Prepare for an interview in a couple of days. [B] Read the advertisement again for more details. [C] Send in a written application as soon as possible. [D] Get to know the candidates on the short list. Section B Directions: In this section, you will hear 3 short passages. At the end of each passage, you will hear some questions. Both the passage and the questions will be spoken only once. After you hear a question, you must choose the best answer from the four choices marked [A], [B], [C] and [D]. Then mark the corresponding letter on Answer Sheet 2 with a single line through the centre. 注意：此部分试题请在答题卡2上作答。 Passage One Questions 26 to 29 are based on the passage you have just heard. 26. [A] They cannot see the firefighters because of the smoke. [B] They do not realize the danger they are in. [C] They cannot hear the firefighters for the noise. [D] They mistake the firefighters for monsters. 27. [A] He travels all over America to help put out fires. [B] He often teaches children what to do during a fire. [C] He teaches Spanish in a San Francisco community. [D] He provides oxygen masks to children free of charge. 28. [A] He saved the life of his brother choking on food. [B] He rescued a student from a big fire. [C] He is very good at public speaking. [D] He gives informative talks to young children. 29. [A] Firefighters play an important role in America. [B] Kids should learn not to be afraid of monsters. [C] Carelessness can result in tragedies. [D] Informative speeches can save lives. Passage Two Questions 30 to 32 are based on the passage you have just heard. 30. [A] To satisfy the needs of their family. [B] To fully realize their potential. [C] To make money for early retirement. [D] To gain a sense of their personal worth. 31. [A] They may have to continue to work in old age. [B] They may regret the time they wasted. [C] They may have nobody to depend on in the future. [D] They may have fewer job opportunities. 32. [A] Making wise use of your time. [B] Enjoying yourself while you can. [C] Saving as much as you can. [D] Working hard and playing hard. Passage Three Questions 33 to 35 are based on the passage you have just heard. 33. [A] Hardworking students being accused of cheating. [B] Boy students being often treated as law-breakers. [C] Innocent people being suspected groundlessly. [D] Junior employees being made to work overtime. 34. [A] Forbidding students to take food out of the restaurant. [B] Requesting customers to pay before taking the food. [C] Asking customers to leave their bags on the counters. [D] Allowing only two students to enter at a time. 35. [A] He was taken to the manager. [C] He was asked to leave. [B] He was closely watched. [D] He was overcharged. Section C Directions: In this section, you will hear a passage three times. When the passage is read for the first time, you should listen carefully for its general idea. When the passage is read for the second time, you are required to fill in the blanks numbered from 36 to 43 with the exact words you have just heard. For blanks numbered from 44 to 46 you are required to fill in the missing information. For these blanks, you can either use the exact words you have just heard or write down the main points in your own words. Finally, when the passage is read for the third time, you should check what you have written. 注意：此部分试题在答题卡2上作答。 Writing keeps us in touch with other people. We write to communicate with relatives and friends. We write to (36) _____________ our family histories so our children and grandchildren can learn and (37) _____________their heritage (传统). With computers and Internet connections in so many (38) _____________, colleges, business, people e-mailing friends and relatives all the time—or talking to them in writing in online (39) _____________ rooms. It is cheaper than calling long distance, and a lot more (40) _____________ than waiting until Sunday for the telephone (41) _____________ to drop. Students are e-mailing their professors to (42) _____________ and discuss their classroom assignments and to (43) _____________ them. They are e-mailing classmates to discuss and collaborate (合作) on homework. (44) __________________________________________________________. Despite the growing importance of computers, however, there will always be a place and need for the personal letter. (45) ____________________________________________________. No matter what the content of the message, its real point is, “I wan t you to know that I care about you.” (46) ____________________________________________________________________, but only in the success of human relationships. Part Ⅳ Reading Comprehension (Reading in Depth) (25 minutes) Section A Directions: In this section, there is a passage with ten blanks. You are required to select one word for each blank from a list of choices given in a word bank following the passage. Read the passage through carefully before making your choices. Each choice in the bank is i dentified by a letter. Please mark the corresponding letter for each item on Answer Sheet 2 with a single line through the centre. You may not use any of the words in the bank more than once. Questions 47 to 56 are based on the following passage. What determines the kind of person you are? What factors make you more or less bold, intelligent, or able to read a map? All of these are influenced by the interaction of your genes and the environment in which you were 47 . The study of how genes and environme nt interact to influence 48 activity is known as behavioral genetics. Behavioral genetics has made important 49 to the biological revolution, providing information about the extent to which biology influences mind, brain and behavior. Any research that suggests that 50 to perform certain behaviors are based in biology is controversial. Who wants to be told that there are limitations to what you can 51 based on something that is beyond your control, such as your genes? It is easy to accept that genes control physical characteristics such as sex, race and eye color. But can genes also determine whether people will get divorced, how 52 they are, or what career they are likely to choose? A concern of psychological scientists is the 53 to which all of these characteristics are influenced by nature and nurture(养育), by genetic makeup and the environment. Increasingly, science 54 that genes lay the groundwork for many human traits. From this perspective, people are born 55 like undeveloped photographs: The image is already captured, but the way it 56 appears can vary based on the development process. However, the basic picture is there from the beginning. 注意：此部分试题请在答题卡2上作答。 [A] abilities [I] extent [B] achieve [J] indicates [C] appeal [K] proceeds [D] complaints [L] psychological [E] contributions [M] raised [F] displayed [N] smart [G] essentially [O] standard [H] eventually Section B Directions: There are 2 passages in this section. Each passage is followed by some questions or unfinished statements. For each of them there are four choices marked [A], [B], [C] and [D]. You should decide on the best choice and mark the corresponding letter on Answer Sheet 2 with a single line through the centre. Passage One Questions 57 to 61 are based on the following passage. It is pretty much a one-way street. While it may be common for university researchers to try their luck in the commercial world, there is very little traffic in the opposite direction. Pay has always been the biggest deterrent, as people with families often feel they cannot afford the drop in salary when moving to a university job. For some industrial scientists, however, the attractions of academia (学术界) outweigh any financial considerations. Helen Lee took a 70% cut in salary when she moved from a senior post in Abbott Laboratories to a medical department at the University of Cambridge. Her main reason for returning to academia mid-career was to take advantage of the greater freedom to choose research questions. Some areas of in quiry have few prospects of a commercial return, and Lee’s is one of them. The impact of a salary cut is probably less severe for a scientist in the early stages of a career. Guy Grant, now a research associate at the Unilever Centre for Molecular Informatics at the University of Cambridge, spent two years working for a pharmaceutical (制药的) company before returning to university as a post-doctoral researcher. He took a 30% salary cut but felt it worthwhile for the greater intellectual opportunities. Higher up the ladder, where a pay cut is usually more significant, the demand for scientists with a wealth of experience in industry is forcing universities to make the transition (转换) to academia more attractive, according to Lee. Industrial scientists tend to receive training that academics do not, such as how to build a multidisciplinary team, manage budgets and negotiate contracts. They are also well placed to bring something extra to the teaching side of an academic role that will help students get a job when they graduate, says Lee, perhaps experience in manufacturing practice or product development. “Only a small number of undergraduates will continue in an academic career. So someone leaving university who already has the skills needed to work in an industrial lab has far more potential in the job market than someone who has spent all their time on a narrow research project.” 注意：此部分试题请在答题卡2上作答。 57. By “a one-way street” (Line 1, Para. 1), the author means ________. [A] university researchers know little about the commercial world [B] there is little exchange between industry and academia [C] few industrial scientists would quit to work in a university [D] few university professors are willing to do industrial research 58. The word “deterrent” (Line 2, Para. 1) most probably refers to something that ________. *A+ keeps someone from taking action *C+ attracts people’s attention [B] helps to move the traffic [D] brings someone a financial burden 59. What was Helen Lee’s major consideratio n when she changed her job in the middle of her career? [A] Flexible work hours. [C] Her preference for the lifestyle on campus. [B] Her research interests. [D] Prospects of academic accomplishments. 60. Guy Grant chose to work as a researcher at Cambridge in order to ________. [A] do financially more rewarding work [B] raise his status in the academic world [C] enrich his experience in medical research [D] exploit better intellectual opportunities 61. What contribution can industrial scientists make when they come to teach in a university? *A+ Increase its graduates’ competitiveness in the job market. *B+ Develop its students’ potential in research. [C] Help it to obtain financial support from industry. [D] Gear its research towards practical applications. Passage Two Questions 62 to 66 are based on the following passage. Being sociable looks like a good way to add years to your life. Relationships with family, friends, neighbours, even pets, will all do the trick, but the biggest longevity (长寿) boost seems to come from marriage or an equivalent relationship. The effect was first noted in 1858 by William Farr, who wrote that widows and widowers (鳏夫) were at a much higher risk of dying than their married peers. Studies since then suggest that marriage could add as much as seven years to a man’s life and two to a woman’s. The effect holds for all causes of death, whether illness, accident or self-harm. Even if the odds are stacked against you, marriage can more than compensate. Linda Waite of the University of Chicago has found that a married older man with heart disease can expect to live nearly four years longer than an unmarried man with a healthy heart. Likewise, a married man who smokes more than a pack a day is likely to l ive as long as a divorced man who doesn’t smoke. There’s a flip side, however, as partners are more likely to become ill or die in the couple of years following their spouse’s death, and caring for a spouse with mental disorder can leave you with some of the same severe problems. Even so, the odds favour marriage. In a 30-year study of more than 10,000 people, Nicholas Christakis of Harvard Medical School describes how all kinds of social networks have similar effects. So how does it work? The effects are complex, affected by socio-economic factors, health-service provision, emotional support and other more physiological (生理的) mechanisms. For example, social contact can boost development of the brain and immune system, leading to better health and less chance of depression later in life. People in supportive relationships may handle stress better. Then there are the psychological benefits of a supportive partner. A life partner, children and good friends are all recommended if you aim to live to 100. The ultimate social network is still being mapped out, but Christakis says: “People are interconnected, so their health is interconnected.” 注意：此部分试题请在答题卡2上作答。 62. William Farr’s study and other studies show that _________. [A] social life provides an effective cure for illness *B+ being sociable helps improve one’s quality of life [C] women benefit more than men from marriage [D] marriage contributes a great deal to longevity 63. Linda Waite’s studies support the idea that _________. [A] older men should quit smoking to stay healthy [B] marriage can help make up for ill health [C] the married are happier than the unmarried [D] unmarried people are likely to suffer in later life 64. It can be inferred from the context that the “flip side” (Line 4, Para. 2) refers to _________. [A] the disadvantages of being married [B] the emotional problems arising from marriage *C+ the responsibility of taking care of one’s family [D] the consequence of a broken marriage 65. What does the author say about social networks? [A] They have effects similar to those of a marriage. *B+ They help develop people’s community spirit. [C] They provide timely support for those in need. *D+ They help relieve people of their life’s burdens. 66. What can be inferred from the last paragraph? *A+ It’s important that we develop a social network when young. [B] To stay healthy, one should have a proper social network. [C] Getting a divorce means risking a reduced life span. [D] We should share our social networks with each other. Part Ⅴ Cloze (15 minutes) Directions: There are 20 blanks in the following passage. For each blank there are four choices marked [A], [B], [C] and [D] on the right side of the paper. You should choose the ONE that best fits into the passage. Then mark the corresponding letter on Answer Sheet 2 with a single line through the centre. 注意：此部分试题请在答题卡2上作答。 Over half the world’s people now live in cities. The latest “Global Report on Human Settlements” says a significa nt change took place last year. The report 67 this week from U.N. Habitat, a United Nations agency. A century ago, 68 than five percent of all people lived in cities. 69 the middle of this century it could be seventy percent, or 70 six and a half billion people. Already three-fourths of people in 71 countries live in cities. Now most urban population 72 is in the developing world. Urbanization can 73 to social and economic progress, but also put 74 on cities to provide housing and 75 . The new report says almost two hundred thousand people move 76 cities and towns each day. It says worsening inequalities, 77 by social divisions and differences in 78 , could result in violence and crime 79 cities plan better. Another issue is urban sprawl (无序扩展的城区). This is where cities 80 quickly into rural areas, sometimes 81 a much faster rate than urban population growth. Sprawl is 82 in the United States. Americans move a lot. In a recent study, Art Hall at the University of Kansas found that people are moving away from the 83 cities to smaller ones. He sees a 84 toward “de-urbanization” across the nation. 85 urban economies still provide many 86 that rural areas do not. 67. [A] came on [B] came off [C] came over[D] came out 68. [A] more [B] other [C] less[D] rather 69. [A] By [B] Through [C] Along[D] To 70. [A] really [B] barely [C] ever[D] almost 71. [A] flourishing [B] developed [C] thriving[D] fertile 72. [A] extension [B] addition [C] raise[D] growth 73. [A] keep [B] turn [C] lead[D] refer 74. [A] pressure [B] load [C] restraint[D] weight 75. [A] surroundings [B] communities [C] concerns[D] services 76. [A] onto [B] into [C] around[D] upon 77. [A] pulled [B] driven [C] drawn[D] pressed 78. [A] situation [B] wealth [C] treasure[D] category 79. [A] when [B] if [C] unless[D] whereas 80. [A] expand [B] split [C] invade[D] enlarge 81. [A] in [B] beyond [C] with[D] at 82. [A] common [B] conventional [C] ordinary[D] frequent 83. [A] essential [B] prior [C] primitive[D] major 84. [A] trend [B] style [C] direction[D] path 85. [A] Then [B] But [C] For[D] While 86. [A] abilities [B] qualities [C] possibilities[D] realities Part VI Translation (5 minutes) Directions: Complete the sentences by translating into English the Chinese given in brackets. Please write your translation on Answer Sheet 2. 注意：此部分试题请在答题卡2上作答，只需写出译文部分。 87. ________________________________________________________(为了确保他参加会议), I called him up in advance. 88. The magnificent museum ________________________________________(据说建成于) about a hundred years ago. 89. There would be no life on earth ___________________________________________(没有地球独特的环境). 90. ___________________________________(给游客印象最深的) was the friendliness and warmth of the local people. 91. They requested that __________________________________________(我借的书还回图书馆) by next Friday. 答案： Help Children to Be Independent Thanks to the “family plan”policy,today in China many families have one child.Loving and caring for children is an old Chinese tradition that has remained for thousands of years.But the children are spoilt so much that they have less independence.They rely on their parents in everything.That is bad for a child's growing.Therefore,parents should develop the children's independence instead of doing everything for them. There are some ways to help children to be independent.First of all,you should believe your children can do the things well.Second,give them more chances to practise,when they don't know how to do it,just tell them the way.Third,don't be afraid to see them fail.In the beginning,they may do something bad.But don't worry,just let them try again.They can do the work as well as you if given more time. To be independent is good for the children.A child who is independent will succeed easily in the future. 快速阅读： 1.people instinctively 2.things purchased 3.more access 4.are less 5.provide 6.they enjoy 7.access to 8.separable things 9.the wild world 10.harmony 听力： 11.A, get 12.B, buying 13.A, taking p 14.B, he 15.D, he 16.C, her gym 17.D, The 18.A，Indifferent. 19.C ，he has 20.B，learn 21.C, every 22.A, what to 23.D. A financial trader 24.B, He considers 25. D, It can 26.D)They mistake the firefighters for monsters。 27.A)He often teaches children what to do during a fire。 28.D)He saved the life of his brother choking on food。 29.D)Informative speeches can save lives。 30.C)To make money for early retirement。 31.A)They may have to continue to work in old age 32.B)Making wise use of your time。 33.C)Innocent people being suspected groundlessly。 34.D)Allowing only two students to enter at a time。 35.B)He was closely watched。 36 international 37 revolution 38 emphasized 39 poor-paying 40 effectively 41 freelancewriter 42 conditioned 43 reasonably 44 The earthquake left thousands of people in urgent need of medicar care. 45 There is no denying the fact that he has directed the most popular film in ten years. 46 A lighted cigarette thrown out of a car or train window can star a fire. 选词填空： 47.raised 48.displayed 49.contributions 50.abilities 51.achieve 52.smart 53.proceeds 54.indicates 55.essentially 56.evevtually 仔细阅读： 57.few…university 58.attracts… 59.her…interests 60.exploit… 61.Increase… 62.marriage…illness 63.marriage…health 64.the…married 65.they…need 66.To… 完形填空： 67.came out 68.less 69.By 70.almost 71.fertile 72.growth 73.lead 74.pressure 75.surroundings 76.into 77.driven 78.treasure 79.when 80.expand 81.at 82.frequent 83.major 84.trend 85.While 86.qualities 87.In order to ensure him to attend the meeting 88.was said to be founded 89.without the special environment on earth 90.what the tourists were impressed by 91.the books that I borrowed be returned to the library 朱雪峰第一题（P35 第4题） 4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值： ①优先顺序（从高至低）为+、*和↑，同级优先采用左结合。 ②优先顺序（从高至低）为↑、+和*，同级优先采用右结合。 朱雪峰第一题（P35 第4题） 解： ① 1+1*2↑2*1↑2 =2*2↑2*1↑2 =4 ↑2*1↑2 =4 ↑2↑2 =16 ↑2=256（+、*和↑，左结合）② 1+1*2↑2*1↑2 = 1+1* 4 *1↑2= 1+1* 4 *1= 2* 4*1=2*4=8（↑、+和*，右结合） 朱雪峰第二题（P36 第6题） 6.令文法G 6为 N →D | ND D →0|1|2|3|4|5|6|7|8|9 ①G 6的语言L(G 6)是什么？ ②给出句子0127、34和568的最左推导和最右推导。 朱雪峰第二题（P36 第6题） 解： ① 根据产生式N →D | ND 可以看出，N 最终可以推出1个或多个（可以是无穷多个）D ，根据产生式D →0|1|2 |3|4|5|6|7|8|9可以看出，每个D 可以推导出0~9中的某一个数字。因此，N 最终推导出的就是由0~9这10个数字组成的字符串。因此G6的语言L(G6)就是由0~9这10个数字组成的字符串。 朱雪峰第二题（P36 第6题） ②句子0127、34和568的最左推导如下： N ?ND ?NDD ?NDDD ?DDDD ?0DDD ?01DD ?012D ?0127 N ?ND ?DD ?3D ?34 N ?ND ?NDD ?DDD ?5DD ?56D ?568 第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题 第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12． 编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 《编译原理》习题答案： 第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？ 答：被翻译的程序称为源程序； 翻译出来的程序称为目标程序或目标代码； 将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序； 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序； 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行； 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。 答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？ 答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。 补充： 2、赋值语句：A：= 5 * C的语法和语义指的是什么？ 答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。第二次作业： P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……} 第2章习题 2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？ (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。 2-2 试分别构造产生下列语言的文法： （1）{a n b n|n≥0}； （2）{a n b m c p|n,m,p≥0}； （3）{a n#b n|n≥0}∪{c n#d n|n≥0}； （4）{w#w r# | w∈{0,1}*,w r是w的逆序排列 }； （5）任何不是以0打头的所有奇整数所组成的集合； （6）所有由偶数个0和偶数个1所组成的符号串的集合。 2-3 试描述由下列文法所产生的语言的特点： （1）S→10S0S→aA A→bA A→a （2）S→SS S→1A0A→1A0A→ε （3）S→1A S→B0A→1A A→C B→B0B→C C→1C0C→ε （4）S→aSS S→a 2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。 2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→c AB|dSD|a D→eA E→fA|g (3) S→ac|bA A→c BC B→SA C→bC|d 2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε 2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 第2章习题答案 2-1 答： (1) 26*26=676 (2) 26*10=260 (3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个 2-2 解： (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S) 编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2: 编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba 1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。 第一章习题解答 1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将 源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。 2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成 程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定 义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。 5.略 第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。 第2章习题解答 1.文法G[S]为： S->Ac|aB A->ab B->bc 写出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为： N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]： S→dAB A→aA|a B→ε|bB 问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案] 正规式是daa*b*； 相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε ===================================================================== ========== 4.已知文法G[Z]： Z->aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n|n>=1} ===================================================================== ========= 5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。 [分析] 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证a n b n的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展] 编译原理复习题 一、是非题 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 3．每个文法都能改写为 LL(1) 文法。 (×) 4．算符优先关系表不一定存在对应的优先函数。 (√) 5．LR分析方法是自顶向下语法分析方法。 (×) 6．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 7．一个句型的句柄一定是文法某产生式的右部。(√) 8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√ ) 9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(× ) 10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× ) 12．递归下降分析法是自顶向下分析方法。(√ ) 13．产生式是用于定义词法成分的一种书写规则。(×) 14．在SLR(1)分析法的名称中，S的含义是简单的。(√) 15．综合属性是用于“ 自上而下” 传递信息。(× ) 16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 17．程序语言的语言处理程序是一种应用软件。(×) 18．解释程序适用于COBOL 和FORTRAN 语言。(×) 19．一个LL(l)文法一定是无二义的。(√) 20．正规文法产生的语言都可以用上下文无关文法来描述。(√) 21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(×) 22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(√) 22．逆波兰法表示的表达式亦称后缀式。(√ ) 23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√ ) 24．数组元素的地址计算与数组的存储方式有关。(√) 25．算符优先关系表不一定存在对应的优先函数。(×) 26．编译程序是对高级语言程序的解释执行。(× ) 27．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 28．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 29．语法分析时必须先消除文法中的左递归。(×) 30．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 31．逆波兰表示法表示表达式时无须使用括号。(√ ) 32．静态数组的存储空间可以在编译时确定。(√) 33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(√) 34．两个正规集相等的必要条件是他们对应的正规式等价。(√) 35．一个语义子程序描述了一个文法所对应的翻译工作。(×) 36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 38．词法分析作为单独的一遍来处理较好。(× ) 39．构造LR分析器的任务就是产生LR分析表。(√) 40．规范归约和规范推导是互逆的两个过程。(√) 41．同心集的合并有可能产生新的“移进”/“归约”冲突。(× ) 第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功 编译原理习题 Revised as of 23 November 2020 一、填空题: 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 . 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码 . 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序 . 1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 . 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 , 汇编阶段和运行阶段 . 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈*} 。 V T 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。 *),则称x是文法2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T 的一个句子。 3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 第二章 2.构造产生下列语言的文法 （2）{a n b m c p|n,m,p≥0} 解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε （3）{a n # b n|n≥0}∪{cn # dn|n≥0} 解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# } （5）任何不是以0 打头的所有奇整数所组成的集合 解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9} （6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合 解：对应文法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B 3.描述语言特点 （2）S→SS S→1A0 A→1A0 A→ε 解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全 为零}该语言特点是：产生的句子中，0、1 个数相同，并且若干相接的1 后必然紧接数量相同连续的0。 （5）S→aSS S→a 解：L(G)={a(2n-1)|n≥1}可知：奇数个a 5. (1) 解：由于此文法包含以下规则：AA→ε，所以此文法是0 型文法。 7.解： (1)aacb 是文法G[S]中的句子，相应语法树是： 最右推导：S=>aAcB=>aAcb=>aacb 最左推导：S=>aAcB=>aacB=>aacb （3）aacbccb 不是文法G[S]中的句子 aacbccb 不能从S推导得到时，它仅是文法G[S]的一个句型的一部分，而不是一个句子。 11.解：最右推导: (1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb 上面推导中，下划线部分为当前句型的句柄。对应的语法树为： 第三章 3 假设M:人 W:载狐狸过河，G:载山羊过河，C:载白菜过河 第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {print″1″} A→(B {print″2″} A→a {print″3″} B→Aa) {print″4″} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L 第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。 一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。《 编译原理》(习题课)(第二章)
编译原理(清华大学第2版)课后习题答案
最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
王汝传编译原理习题答案
蒋立源 编译原理第三版第二章 习题与答案(修改后)
编译原理_第三版_课后答案
编译原理复习题及答案
哈工大编译原理习题及答案
编译原理 第二章习题答案
最新编译原理复习题(经典)
编译原理课后习题答案-清华大学-第二版
编译原理习题
编译原理习题集
编译原理教程课后习题答案——第四章
编译原理习题及答案(整理后)
编译原理课后习题答案+清华大学出版社第二版