I'm trying to implement syntax highlighting for text in a Text widget. 
I use an external library to lexically analyse the text and give me the tokenised text. After that I go over all the words in the text and apply tag to their position in the text widget so that I can style each word. 
My concern now is how do I deal with changes. Every time the user presses a key, do I tokenise the entire text again and add style tags to the text widget for the entire text. This is proving to be quite slow. 
I then transitioned to only doing the highlighting process for the line the insert character was to make it faster but this is giving faulty results and the highlighting is not perfect now. 
What would be an ideal compromise between fast and perfect? What is the best way to do this?
One possible answer is to do something like Idle does.  As a user hits each key, its custom incremental parser tags identifiers that are a keyword, builtin, or def/class name*.  It also tags delimited char sequences that are a string or comment. I does what can be done quickly enough.
For example, if one types printer not in a string or comment, Idle checks if the word is a keyword or builtin name after each key.  After t is hit, print is tagged.  After e (or any other identifier char) is entered, printe is untagged. 
I believe some of the code is in idlelib/Hyperparser.py and some in ColorDelegator.py.  You are free to copy and adapt code, but please do not use it directly, as the API may change.  I presume the parser does the minimum needed according to the current state (after def/class, in an identifier, comment, string, etc.)
Idle has an re-based function to retag the entire file.  I 'think' this is separate from the incremental colorizer, but I have not read all the relevant code. If one edits a long enough file, such as idlelib/EditorWindow.py (about 3000 lines), and changes font size, Idle retags the file (I am not sure why).  There is a noticeable delay between the file turning all black and its being recolorized.  You definitely would not want that delay with each keystroke.

Class/functions names with non-ascii chars are not yet properly recognized in 3.x, but should be.  The patch is stuck on deciding the faster accurate method. Recognizing an ascii-only (2.x) indentifier is trivial by comparison.

PS  I am correctly in guessing that you are interested in tagging something other than Python code?
Efficiently applying text widget tags in tkinter text widgets